Sum of Domination and Independence Numbers of Cubic Bipartite Graphs

Rekha Lahoti, Omprakash Prakash Sikhwal, Sapna Shrimali


The fastest growing area within graph theory is the study of domination and Independence numbers, the reason being its many and varied applications in such fields as social sciences, communications networks, algorithmic designs etc. A subset D of V is a dominating set of G if every vertex of V- D is adjacent to a vertex of D. The domination number of G, denoted by γ (G), is the minimum cardinality of a dominating set of G. Domination number is the cardinality of a minimum dominating set of a graph. Independence number is the maximal cardinality of an independent set of vertices of a graph. In this paper we present results on domination and independence numbers of cubic bipartite graphs.

Full Text:



B. Zelinka, “Some remarks on domination in cubic graphs”, Discrete Mathematics, 158, 1996, 249-255.

C. Payan and N. H. Xuong, “Domination-balanced graphs”, J. Graph Theory 6, 1982, 23-32.

E. J. Cockayne and S. T. Hedetniemi, “Towards a theory of domination in graphs”, Networks, 7, 1977, 247-261.

F. S. Roberts, “Graph theory and its application to problems of society”, SIAM, Philadelphia, 1978, 57-64.

J.F. Fink, M.S. Jacobson, L. Kinch and J. Roberts, “On graphs having domination number half their order”, Period. Math. Hungar, 16, 1985, 287–293.

M. Blidia, M. Chellali and O. Favaron, “Independence and 2-domination in trees”, Australas. J. Combin. 33, 2005, 317–327.

N. Murugesan and Deepa S. Nair “The Domination and Independence of Some Cubic Bipartite Graphs” Int. J. Contemp. Math. Sciences, Vol.6, no. 13, 2011, pp. 611 – 618.

Narsingh Deo, “Graph Theory with Applications to Engineering and Comp.Science”, Prentice Hall, Inc., USA ,1974.

O. Ore, “Theory of Graphs”, Amer. Math. Soc. Colloq. Publ. 38, (1962).

T.W Haynes, S.T. Hedetniemi S. T. and P. J. Slater. “Fundamentals of domination in Graphs”, Marcel Dekker, New York, 1998.

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, “Domination in graphs, Advanced Topics”, Marcel Dekker, New York, 1998.

Vasumathi, N., and Vangipuram, S., Existence of a graph with a given domination parameter, Proceedings of the Fourth Ramanujan Symposium on Algebra and its Applications, University of Madras, Madras, 187-195 (1995).

Vijaya Saradhi and Vangipuram, Irregular graphs‟. Graph Theory Notes of New York, Vol. 41, 33-36, (2001).


  • There are currently no refbacks.

MAYFEB Journal of Mathematics 
Toronto, Ontario, Canada
ISSN 2371-6193