DOMINATION AND EDGE DOMINATION IN TREES

B. Senthilkumar     (SASTRA Deemed University, Tanjore, Tamilnadu, India)
Yanamandram B. Venkatakrishnan     (SASTRA Deemed University, Tanjore, Tamilnadu, India)
H. Naresh Kumar     (SASTRA Deemed University, Tanjore, Tamilnadu, India)

Abstract


Let \(G=(V,E)\) be a simple graph. A set \(S\subseteq V\) is a dominating set if every vertex in \(V \setminus S\) is adjacent to a vertex in \(S\). The domination number of a graph \(G\), denoted by \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). A set \(D \subseteq E\) is an edge dominating set if every edge in \(E\setminus D\) is adjacent to an edge in \(D\). The edge domination number of a graph \(G\), denoted by \(\gamma'(G)\) is the minimum cardinality of an edge dominating set of \(G\). We characterize trees with  domination number equal to twice edge domination number.

Keywords


Edge dominating set, Dominating set, Trees.

Full Text:

PDF

References


Arumugam S., Velammal S. Edge domination in graphs. Taiwanese J. Math., 1998. Vol. 2, No. 2. P. 173–179. URL: https://www.jstor.org/stable/43834391

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

Haynes T.W., Hedetniemi S.T., Slater P.J. Domination in Graphs: Advanced Topics. New York: Marcel Dekker, 1998. 497 p.

Krishnakumari B., Venkatakrishnan Y.B. and Krzywkowski M. On trees with total domination number equal to edge-vertex domination number plus one. Proc. Math. Sci., 2016. Vol. 126. P. 153–157. DOI: 10.1007/s12044-016-0267-6

Liu C.L. Introduction to Combinatorial Mathematics. New York: McGraw Hill, 1968. 393 p.

Dorfling M., Goddard W., Henning M.A., Mynhardt C.M. Construction of trees and graphs with equal dominating parameters. Discrete Math., 2006. Vol. 306, No. 21. P. 2647–2654. DOI: 10.1016/j.disc.2006.04.031

Meddah N., Chellali M. Edges contained in all or in no minimum edge dominating set of a tree. Discrete Math. Algorithms Appl., 2019. Vol. 11, No. 4. Art. no. 1950040. DOI: 10.1142/S179383091950040X

Venkatakrishnan Y.B., Krishnakumari B. An improved upper bound of edge-vertex domination number of a tree. Inform. Process. Lett., 2018. Vol. 134. P. 14–17. DOI: 10.1016/j.ipl.2018.01.012




DOI: http://dx.doi.org/10.15826/umj.2020.1.012

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.