2023/08/29 by Akbari, S., Azimian, M., Khani, A. Fazli +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.15114
Let G be a graph. A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex in S. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a 3-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace 3-cycle with 4-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order 4 minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017.