Abstract
A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. In this paper, we consider questions about independent domination in regular graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barefoot C., Harary F., Jones K.F.: What is the difference between the domination and independent domination numbers of cubic graph?. Graphs Combin. 7(2), 205–208 (1991)
Berge C.: Theory of Graphs and its Applications. Methuen & Co. Ltd., London (1962)
Cockayne E.J., FavaronO. , Li H., MacGillivray G.: The product of the independent domination numbers of a graph and its complement. Discrete Math. 90(3), 313–317 (1991)
Cockayne E.J., Fricke G., Mynhardt C.M.: On a Nordhaus-Gaddum type problem for independent domination. Discrete Math. 138(1-3), 199–205 (1995)
Cockayne E.J., Hedetniemi S.T.: Independence graphs. Congr. Numer. X, 471–491 (1974)
Cockayne E.J., Hedetniemi S.T.: Towards a theory of domination in graphs. Networks 7(3), 247–261 (1977)
Cockayne E.J., Mynhardt C.M.: Independence and domination in 3-connected cubic graphs. J. Combin. Math. Combin. Comput. 10, 173–182 (1991)
Duckworth, W.,Wormald, N.: Linear programming and the worst-case analysis of greedy algorithms on cubic graphs. Electron. J. Combin. 17(1), #R177 (2010)
Favaron O.: Two relations between the parameters of independence and irredundance. Discrete Math. 70(1), 17–20 (1988)
Gimbel J., Vestergaard P.D.: Inequalities for total matchings of graphs. Ars Combin. 39, 109–119 (1995)
Goddard W., Henning M.A.: Nordhaus-Gaddum bounds for independent domination. Discrete Math. 268, 299–302 (2003)
Harutyunyan, A., Horn, P., Verstraete, J.: Independent dominating sets in graphs of girth five. Avaible at: http://www.math.ucsd.edu/jverstra/indom-final.pdf (2010)
Haviland J.: On minimum maximal independent sets of a graph. Discrete Math. 94, 95–101 (1991)
Haviland J.: Independent domination in regular graphs. Discrete Math. 143, 275–280 (1995)
Haviland J.: Upper bounds for independent domination in regular graphs. Discrete Math. 307, 2643–2646 (2007)
Haynes T.W., Hedetniemi S.T., Slater P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)
Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York (1998)
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)
Lam P.C.B., Shiu W.C., Sun L.: On independent domination number of regular graphs. Discrete Math. 202, 135–144 (1999)
Rabern L.: On hitting all maximum cliques with an independent set. J. Graph Theory 66, 32–37 (2011)
Rosenfeld M.: Independent sets in regular graphs. Israel J. Math. 2, 262–272 (1964)
Seifter N.: Domination and independent domination numbers of graphs. Ars Combin. 38, 119–128 (1994)
Verstraete, J.: Personal communication. (2010)
Žerovnik J., Oplerova J.: A counterexample to conjecture of Barefoot, Harary, and Jones. Graphs Combin. 9, 205–207 (1993)
Zverovich I.È., Zverovich V.È.: Disproof of a conjecture in the domination theory. Graphs Combin. 10, 389–396 (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by the South African National Research Foundation.
Rights and permissions
About this article
Cite this article
Goddard, W., Henning, M.A., Lyle, J. et al. On the Independent Domination Number of Regular Graphs. Ann. Comb. 16, 719–732 (2012). https://doi.org/10.1007/s00026-012-0155-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-012-0155-4