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 G = ( V , E ) {\displaystyle G=(V,E)} be a graph. A vertex v ∈ V {\displaystyle v\in V} is called a support vertex if v {\displaystyle v} is adjacent to at least one leaf of G {\displaystyle G} . 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 T {\displaystyle T} of order n {\displaystyle n} has a perfect matching if and only if γ t gr ( T ) = n {\displaystyle \gamma _{t}^{\text{gr}}(T)=n} , where γ t gr {\displaystyle \gamma _{t}^{\text{gr}}} 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 γ t gr ( T ) ≥ 2 3 ( n + 1 ) {\displaystyle \gamma _{t}^{\text{gr}}(T)\geq {\tfrac {2}{3}}(n+1)} holds.
See also Leaf (graph theory) Dominating set
References
