Vertex cover and Edge vertex domination in trees
DOI:
https://doi.org/10.22199/issn.0717-6279-3532Keywords:
Edge vertex dominating set, Vertex cover, TreesAbstract
Let G = (V,E) be a simple graph. An edge e ∈ E(G) edge-vertex dominates a vertex v ∈ V (G) if e is incident with v or e is incident with a vertex adjacent to v. A subset D ⊆ E(G) is an edge-vertex dominating set of a graph G if every vertex of G is edge-vertex dominated by an edge of D. A vertex cover of G is a set C ⊆ V such that for each edge uv ∈ E at least one of u and v is in C. We characterize trees with edge-vertex domination number equals vertex covering number.
References
R. Dutton and W. F. Klostermeyer, “Edge dominating sets and Vertex Covers”, Discussiones Mathematicae Graph Theory, vol. 33, pp. 437-456, 2013.
W. F. Klostermeyer, M. E. Messinger and A. Yeo, “Dominating Vertex Covers: The Vertex-Edge Domination Problem”, Discussiones Mathematicae Graph Theory, vol. 41, pp. 123-132, https://doi.org/10.7151/dmgt.2175
B. Krishnakumari, Y. B. Venkatakrishnan and M. Krzywkowski, “On trees with total domination number equal to edge-vertex domination number plus one”, Proceedings - Mathematical Sciences, vol. 126, pp. 153-157, 2016.
J. R. Lewis, "Vertex-edge and edge-vertex parameters in graphs", Ph. D. Thesis, Clemson University, 2007.
K. W. Peters, “Theoretical and Algorithmic Results on Domination and Connectivity”, Ph.D. Thesis, Clemson University, 1986.
Y. B. Venkatakrishnan and B. Krishnakumari, “An improved upper bound of edge-vertex domination number of a tree”, Information Processing Letters, vol. 134, pp. 14-17, 2018.
Published
How to Cite
Issue
Section
Copyright (c) 2021 B. Senthilkumar, H. Naresh Kumar, Y. B. Venkatakrishnan
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.