Graph theoretic name for minimal subgraph that connects to full graph

61 Views Asked by At

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

There are 1 best solutions below

2
On BEST 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).$