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


  1. 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
  2. Haynes T.W., Hedetniemi S.T., Slater P.J. Fundamentals of Domination in Graphs. New York: Marcel Dekker, 1998. 455 p.
  3. Haynes T.W., Hedetniemi S.T., Slater P.J. Domination in Graphs: Advanced Topics. New York: Marcel Dekker, 1998. 497 p.
  4. 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
  5. Liu C.L. Introduction to Combinatorial Mathematics. New York: McGraw Hill, 1968. 393 p.
  6. 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
  7. 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
  8. 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.