# Graph theoretic name for minimal subgraph that connects to full graph

Let $G$ be a graph with vertices $V$ and edge set $E$. Define $T$ to be the minimal subgraph of $G$ (in terms of number of vertices), such that every vertex $v\in V\backslash T$ connects to at least one vertex of $T$, via an edge $e\in E$. For example, if $G=K_n$ is a complete graph, then $T$ can be a single vertex, since it connects to every other vertex. Or if $G$ is a square graph on 4 vertices, $T$ can be the two vertices diagonally opposite of each other.

Is there a common name for $T$ in graph-theory literature?

## 1 Answer

A set $T\subseteq V(G)$ with the property, that every vertex $v\in V\setminus T$ is adjacent to at least one vertex in $T,$ is called a dominating set. A dominating set of minimum cardinality is called a minimum dominating set. The minimum number of vertices in a dominating set is called the domination number of the graph, in symbols $\gamma(G).$

• Perfect. Thanks! – Alex R. May 21 '18 at 6:38
• @AlexR. You're welcome. I changed my answer slightly; the term "minimum dominating set" seems to be reasonably standard. – bof May 21 '18 at 6:47