TOPICS
Search

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.

It is NP-complete to test if there exists a connected dominating set having size less than some given value.


See also

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

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Connected Dominating Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConnectedDominatingSet.html

Subject classifications