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.¹

Let ${\displaystyle G=(V,E)}$ be a graph. A vertex ${\displaystyle v\in V}$ is called a support vertex if ${\displaystyle v}$ is adjacent to at least one leaf of ${\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.²

• 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 ${\displaystyle T}$ of order ${\displaystyle n}$ has a perfect matching if and only if ${\displaystyle \gamma _{t}^{\text{gr}}(T)=n}$, where ${\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 ${\displaystyle \gamma _{t}^{\text{gr}}(T)\geq {\tfrac {2}{3}}(n+1)}$ holds.⁴