Edge domination in various snake graphs

S K Vaidya, R M Pandit


A subset of the edge set of G is an edge dominating set if each edge in E(G) is either in F or is adjacent to an edge in F. An edge dominating set F is called a minimal edge dominating set if no proper subset of F is an edge dominating set. The edge domination number is the minimum cardinality among all minimal edge dominating sets. We investigate the edge domination number of some graphs called snakes which are obtained from path Pn by replacing its edges by cycles C3 and C4.

Full Text:



S. Arumugam and S. Jerry, Fractional edge domination in graphs, Appl. Anal. Discrete Math., 3 (2009), 359-370. doi : 10.2298/AADM0902359A.

S. Arumugam and S. Velammal, Edge domination in graphs, Taiwanese J. Math., 2 (1998), 173-179.

R. Dutton and W. Klostermeyer, Edge dominating sets and vertex covers, Discussiones Mathematicae, 33 (2013), 437-456. doi : 10.7151/dmgt.1681.

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

S. T. Hedetniemi and R. C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math., 86 (1990), 257-277.

S. R. Jayaram, Line domination in graphs, Graphs Combin., 3 (1977), 489-509.

V. R. Kulli and N. D. Soner, Complementary edge domination in graphs, Indian Journal pure and appl. Math., 28 (1997), 917-920.

S. Mitchell and S. T. Hedetniemi, Edge domination in trees, Congr. Numer., 19 (1977), 489-509.

D. A. Mojdeh and R. Sadeghi, Independent edge dominating set of certain graphs, International Mathematical Forum, 2 2007), 315-320.

S. K. Vaidya and R. M. Pandit, Edge domination in splitting graphs, International Journal of Mathematics and Scientific Computing, 4 (2014), 39-42.

S. K. Vaidya and R. M. Pandit, Edge domination in some path and cycle related graphs, ISRN Discrete Mathematics, vol. 2014, Article ID 975812, (2014), 5 pages.

D. B. West, Introduction to Graph Theory, Prentice - Hall of India, New Delhi, 2003.

M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math., 38 (1980), 364-372.

B. Zelinka, Edge domination in graphs of cubes, Czechoslovak Mathematical Journal, 52 (2002), 875-879.


  • There are currently no refbacks.

Web Counters

IJMSC has been indexed in several world class data bases like Google Scholar , DOAJ(Directory of Open Access Journals), DRJI (Directory of Research Journals Indexing) ,Cite Factor, Research Bible.