Edge domination in various snake graphs

S K Vaidya, R M Pandit


A set $F \subseteq E(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 $F ^ \prime$ of $F$ is an edge dominating set. The edge domination number $\gamma ^\prime(G)$ 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 $P_n$ by replacing its edges by cycles $C_3$ and $C_4$.

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, DRJI (Directory of Research Journals Indexing) ,Cite Factor, Research Bible.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.