Support vertex
In graph theory, a support vertex is a vertex that is adjacent to a leaf (a vertex of degree one). Support vertices play an important role in the study of domination in graphs, since every support vertex must belong to every minimum dominating set.
Definition
Let be a graph. A vertex is called a support vertex if is adjacent to at least one leaf of .
A support vertex is called a weak support vertex if it is adjacent to exactly one leaf, and a strong support vertex if it is adjacent to two or more leaves.
Properties
- Every support vertex belongs to every minimum dominating set of a graph.
- If a graph has no weak support vertex, then its domination number equals its certified domination number.
- Every support vertex belongs to every minimum certified dominating set of a graph.
- A tree of order has a perfect matching if and only if , where denotes the Grundy total domination number. The characterization of trees achieving the lower bound for this parameter involves the structure of support vertices: among trees with no strong support vertex, the bound holds.
See also
References
- 1 2 3 Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (2023). Fundamentals of Domination in Graphs. Springer. doi:10.1007/978-3-031-09496-5_2.
- ↑ Raczek, Joanna; Miotk, Mateusz (2025). "Two Approaches to Constructing Certified Dominating Sets in Social Networks". IEEE Access. 13: 17495–17505. doi:10.1109/ACCESS.2025.3532392.
- 1 2 Dettlaff, Magda; Lemańska, Magdalena; Topp, Jerzy; Ziemann, Radosław; Żyliński, Paweł (2020). "Certified domination". AKCE International Journal of Graphs and Combinatorics. 17 (1): 86–97. arXiv:1606.03257. doi:10.1016/j.akcej.2018.09.004.
- ↑ Haynes, Teresa W.; Hedetniemi, Stephen T. (2021). "Vertex Sequences in Graphs". Discrete Mathematics Letters. 6: 19–31. doi:10.47443/dml.2021.s103.
 | This graph theory-related article is a stub. You can help Wikipedia by adding missing information. |