Connected Dominating Set

A connected dominating set in a connected graph G is a dominating set in G whose vertices induce a connected subgraph, i.e., one in which there is no dominating vertex not connected to some other dominating vertex by an edge. Connected dominating sets therefore comprise a subset of all dominating sets in a graph.

A minimum connected dominating set of a graph G is a connected dominating set of smallest possible size, where the minimum size is denoted d(G) and known as the connected domination number.

See also

Connected Domination Number, Connected Graph, Dominating Set, Domination Number, Domination Polynomial

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Connected Dominating Set." From MathWorld--A Wolfram Web Resource.

Subject classifications