Graphs with Equal Domination and Independent Domination Number

Year 2015, Volume: 5 Issue: 1, 74 - 79, 01.06.2015

S. K. Vaidya R. M. Pandit

Abstract

A set S of vertices of a graph G is an independent dominating set of G ifS is an independent set and every vertex not in S is adjacent to a vertex in S. Theindependent domination number of G, denoted by i G , is the minimum cardinality ofan independent dominating set of G. In this paper, some new classes of graphs withequal domination and independent domination numbers are presented and exact valuesof their domination and independent domination numbers are determined

Keywords

Dominating set, domination number, independent dominating set, independent domination number

References

• Acharya, B. D. and Gupta, P., (2003), On graphs whose domination numbers equal their independent domination numbers, Electronic Notes in Discrete Math., 15, pp. 2-4.
• Allan, R. B. and Laskar, R., (1978), On domination and independent domination numbers of a graph, Discrete Math., 23, pp. 73-76.
• Ao, S., Cockayne, E. J., MacGillivray, G. and Mynhardt, C. M., (1996), Domination critical graphs with higher independent domination numbers, J. Graph Theory, 22, pp. 9-14.
• Berge, C., (1962), Theory of Graphs and its Applications, Methuen, London.
• Cockayne, E. J. and Hedetniemi, S. T., (1974), Independent graphs, Congr. Numer., X, pp. 471-491. [6] Cockayne, E. J. and Hedetniemi, S. T., (1977), Towards a theory of domination in graphs, Networks 7, pp. 247-261.
• Favaron, O., (1988), Two relations between the parameters of independence and irredundance, Discrete Math., 70, pp. 17-20.
• Goddard, W., Henning, M., Lyle, J. and Southey, J., (2012), On the independent domination number of regular graphs, Ann. Comb., 16, pp. 719-732.
• Goddard, W. and Henning, M., (2013), Independent domination in graphs: A survey and recent results, Discrete Math., 313, pp. 839-854.
• Haviland, J., (1995), Independent domination in regular graphs, Discrete Math., 143, pp. 275-280.
• Haxell, P., Seamone, B. and Verstra¨ete, J., (2007), Independent dominating sets and Hamiltonian cycles, J. Graph Theory, 54, pp. 233-244.
• Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., (1998), Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York.
• Kostochka, A. V., (1993), The independent domination number of a cubic 3-connected graph can be much larger than its domination number, Graphs Combin., 9, pp. 235-237.
• Ore, O., (1962), Theory of graphs, Amer. Math. Soc. Transl., 38, pp. 206-212.
• Shiu, W. C., Chen, X. and Chan, W. H., (2010), Triangle-free graphs with large independent domi- nation number, Discrete Optim., 7, pp. 86-92.
• Sun, L. and Wang, J., (1999), An upper bound for the independent domination number, J. Combin. Theory. Ser., B76, pp. 240-246.
• Topp, J. and Volkmann, L., (1991), On graphs with equal domination and independent domination numbers, Discrete Math., 96, pp. 75-80.
• West, D. B., (2003), Introduction to Graph Theory, Prentice-Hall of India, New Delhi.