×

zbMATH — the first resource for mathematics

On the independent domination number of regular graphs. (English) Zbl 1256.05169
Summary: 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.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] 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) · Zbl 0728.05033
[2] Berge C.: Theory of Graphs and its Applications. Methuen & Co. Ltd., London (1962) · Zbl 0097.38903
[3] 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) · Zbl 0736.05068
[4] 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) · Zbl 0820.05039
[5] Cockayne E.J., Hedetniemi S.T.: Independence graphs. Congr. Numer. X, 471–491 (1974) · Zbl 0305.05114
[6] Cockayne E.J., Hedetniemi S.T.: Towards a theory of domination in graphs. Networks 7(3), 247–261 (1977) · Zbl 0384.05051
[7] 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
[8] Duckworth, W.,Wormald, N.: Linear programming and the worst-case analysis of greedy algorithms on cubic graphs. Electron. J. Combin. 17(1), #R177 (2010) · Zbl 1204.05090
[9] Favaron O.: Two relations between the parameters of independence and irredundance. Discrete Math. 70(1), 17–20 (1988) · Zbl 0639.05029
[10] Gimbel J., Vestergaard P.D.: Inequalities for total matchings of graphs. Ars Combin. 39, 109–119 (1995) · Zbl 0837.05085
[11] Goddard W., Henning M.A.: Nordhaus-Gaddum bounds for independent domination. Discrete Math. 268, 299–302 (2003) · Zbl 1022.05057
[12] 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)
[13] Haviland J.: On minimum maximal independent sets of a graph. Discrete Math. 94, 95–101 (1991) · Zbl 0758.05061
[14] Haviland J.: Independent domination in regular graphs. Discrete Math. 143, 275–280 (1995) · Zbl 0838.05065
[15] Haviland J.: Upper bounds for independent domination in regular graphs. Discrete Math. 307, 2643–2646 (2007) · Zbl 1127.05072
[16] Haynes T.W., Hedetniemi S.T., Slater P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York (1998) · Zbl 0883.00011
[17] Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York (1998) · Zbl 0890.05002
[18] 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
[19] 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
[20] Rabern L.: On hitting all maximum cliques with an independent set. J. Graph Theory 66, 32–37 (2011) · Zbl 1222.05201
[21] Rosenfeld M.: Independent sets in regular graphs. Israel J. Math. 2, 262–272 (1964) · Zbl 0134.43501
[22] Seifter N.: Domination and independent domination numbers of graphs. Ars Combin. 38, 119–128 (1994) · Zbl 0815.05037
[23] Verstraete, J.: Personal communication. (2010)
[24] Žerovnik J., Oplerova J.: A counterexample to conjecture of Barefoot, Harary, and Jones. Graphs Combin. 9, 205–207 (1993) · Zbl 0777.05075
[25] 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.