Overview
(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 .
Properties
* Every support vertex belongs to every minimum 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