Connected Domination Number

The connected domination number of a connected graph G, denoted d(G), is the size of a minimum connected dominating set of a graph G.

The maximum leaf number l(G) and connected domination number of a graph G are connected by


where n=|G|>2 is the vertex count of G.

Many families of graphs have simple closed forms, as summarized in the following table. In the table, |_x_| denotes the floor function.

See also

Connected Dominating Set, Dominance, Dominating Set, Domination Number, Domination Polynomial, Maximum Leaf Number

Explore with Wolfram|Alpha


Sampathkumar, E.; and Walikar, H. B. "The Connected Domination Number of a Graph." J. Math. Phys. Sci. 13, 607-613, 1979.

Cite this as:

Weisstein, Eric W. "Connected Domination Number." From MathWorld--A Wolfram Web Resource.

Subject classifications