Total Domination Versus Domination in Cubic Graphs
Joanna Cyman, Magda Dettlaff, Michael A. Henning, Magdalena Lemańska, Joanna Raczek · Graphs and Combinatorics · 2017
A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, $$\gamma (G)$$ , and total domination number, $$\gamma _{t}(G)$$ , are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, $$\Gamma (G)$$ , and the upper total domination number, $$\Gamma _t(G)$$ , are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that $$\gamma _{t}(G)/\gamma (G) \le 2$$ and $$\Gamma _{t}(G)/\Gamma (G) \le 2$$ for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying $$\gamma _{t}(G)/\gamma (G) = 2$$ , and we characterize the connected cubic graphs G satisfying $$\Gamma _{t}(G)/\Gamma (G) = 2$$ .