Total domination and vertex-edge domination in trees.
Keywords:
Vertex-edge dominating set, Total dominating set, TreesAbstract
A vertex v of a graph G = (V,E) is said to ve-dominate every edge incident to v, as well as every edge adjacent to these incident edges. A set S ⊆ V is a vertex-edge dominating set if every edge of E is ve-dominated by at least one vertex of S. The minimum cardinality of a vertex-edge dominating set of G is the vertex-edge domination number γve(G) . In this paper we prove (γt(T)−ℓ+1)/2 ≤ γve(T) ≤(γt(T)+ℓ−1)/2 and characterize trees attaining each of these bounds.Downloads
References
R. Boutrig, M. Chellali, T. W. Haynes and S. T. Hedetniemi, Vertexedge domination in graphs. Aequat. Math., 90, pp. 355—366, (2016).
M. A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics). 2013. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online).
B. Krishnakumari, Y. B. Venkatakrishnan and M. Krzywkowski, Bounds on the vertex-edge domination number of a tree. C. R. Acad. Sci. Paris, Ser.I 352, pp. 363—366, (2014).
J. R. Lewis, S. T. Hedetniemi, T. W. Haynes and G. H. Fricke, Vertexedge domination. Util. Math. 81, pp. 193—213, (2010).
J. W. Peters. Theoretical and algorithmic results on domination and connectivity. Ph.D. Thesis, Clemson University, (1986).
Downloads
Published
Issue
Section
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.