Support vertex

Each blue vertex in the graph shown is a support vertex, adjacent to at least one leaf (highlighted green). The darker blue vertex is a strong support vertex, and the two lighter blue vertices are weak support vertices.

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

See also

• Leaf (graph theory)
• Dominating set