1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.