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.^[1]

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}$.^[1]

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.^[2]

• Every support vertex belongs to every minimum dominating set of a graph.^[1]
• If a graph has no weak support vertex, then its domination number equals its certified domination number.^[3]
• Every support vertex belongs to every minimum certified dominating set of a graph.^[3]
• 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.^[4]

• Leaf (graph theory)
• Dominating set