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 1


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

  • $\begingroup$ Perfect. Thanks! $\endgroup$
    – Alex R.
    May 21, 2018 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, 2018 at 6:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .