zbMATH — the first resource for mathematics

Domination versus independent domination in cubic graphs. (English) Zbl 1277.05129
Summary: A set $$S$$ of vertices in a graph $$G$$ is a dominating set if every vertex not in $$S$$ is adjacent to a vertex in $$S$$. If, in addition, $$S$$ is an independent set, then $$S$$ is an independent dominating set. The domination number $$\gamma (G)$$ of $$G$$ is the minimum cardinality of a dominating set in $$G$$, while the independent domination number $$i(G)$$ of $$G$$ is the minimum cardinality of an independent dominating set in $$G$$. In this paper we show that if $$G\neq K(3,3)$$ is a connected cubic graph, then $$i(G)/\gamma (G)\leq 4/3$$. This answers a question posed by W. Goddard et al. in [Ann. Comb. 16, No. 4, 719–732 (2012; Zbl 1256.05169)] where the bound of $$3/2$$ is proven. In addition we characterize the graphs achieving this ratio of $$4/3$$.

MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Zbl 1256.05169
Full Text:
References:
 [1] Ao, S.; Cockayne, E. J.; MacGillivray, G.; Mynhardt, C. M., Domination critical graphs with higher independent domination numbers, J. Graph Theory, 22, 9-14, (1996) · Zbl 0852.05053 [2] Barefoot, C.; Harary, F.; Jones, K. F., What is the difference between the domination and independent domination numbers of cubic graph?, Graphs Combin., 7, 205-208, (1991) · Zbl 0728.05033 [3] Berge, C., Theory of graphs and its applications, (1962), Methuen London · Zbl 0097.38903 [4] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261, (1977) · Zbl 0384.05051 [5] Cockayne, E. J.; Mynhardt, C. M., Independence and domination in 3-connected cubic graphs, J. Combin. Math. Combin. Comput., 10, 173-182, (1991) · Zbl 0763.05094 [6] W. Goddard, M.A. Henning, J. Lyle, J. Southey, On the independent domination number of regular graphs, Ann. Comb. (in press). · Zbl 1256.05169 [7] Haviland, J., Independent domination in regular graphs, Discrete Math., 143, 275-280, (1995) · Zbl 0838.05065 [8] Haviland, J., Upper bounds for independent domination in regular graphs, Discrete Math., 307, 2643-2646, (2007) · Zbl 1127.05072 [9] Haxell, P.; Seamone, B.; Verstraete, J., Independent dominating sets and Hamiltonian cycles, J. Graph Theory, 54, 233-244, (2007) · Zbl 1112.05077 [10] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002 [11] (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics, (1998), Marcel Dekker New York) · Zbl 0883.00011 [12] Kostochka, A. V., The independent domination number of a cubic 3-connected graph can be much larger than its domination number, Graphs Combin., 9, 235-237, (1993) · Zbl 0783.05062 [13] Lam, P. C.B.; Shiu, W. C.; Sun, L., On independent domination number of regular graphs, Discrete Math., 202, 135-144, (1999) · Zbl 0934.05098 [14] J. Lyle, W. Goddard, Independent domination in regular graphs (in preparation). · Zbl 1245.90134 [15] Ore, O., Theory of graphs, Amer. Math. Soc. Transl., 38, 206-212, (1962) [16] Shiu, W. C.; Chen, X.; Chan, W. H., Triangle-free graphs with large independent domination number, Discrete Optim., 7, 86-92, (2010) · Zbl 1264.05095 [17] Sun, L.; Wang, J., An upper bound for the independent domination number, J. Combin. Theory Ser. B, 76, 240-246, (1999) · Zbl 0933.05118 [18] Žerovnik, J.; Oplerova, J., A counterexample to conjecture of barefoot, harary, and Jones, Graphs Combin., 9, 205-207, (1993) · Zbl 0777.05075 [19] Zverovich, I.È.; Zverovich, V.È., Disproof of a conjecture in the domination theory, Graphs Combin., 10, 389-396, (1994) · Zbl 0813.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.