Vertex cover and Edge vertex domination in trees
Keywords:Edge vertex dominating set, Vertex cover, Trees
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.
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.
How to Cite
Copyright (c) 2021 B. Senthilkumar, H. Naresh Kumar, Y. B. Venkatakrishnan
This work is licensed under a Creative Commons Attribution 4.0 International License.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.