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
| d(G)+l(G)=|G|, |
where n=|G|>2 is the vertex count of G.
It is NP-complete to test if there exists a connected dominating set having size less than some given value.
Many families of graphs have simple closed forms, as summarized in the following table. In the table, |_x_| denotes the floor function.
graph family connected domination number
antiprism graph n-1
black
bishop graph BB_(n,n) [画像:{1 for n=1,2; n-2 otherwise]
book graph S_(n+1) square P_2 2
cocktail party graph K_(n×2) 2
complete bipartite graph K_(n,n) 2
complete
graph K_n 1
complete tripartite graph K_(n,n,n) 2
2n-crossed prism graph 2n
crown
graph K_2 square K_n^_ 4
cycle
graph C_n n-2
gear
graph 1+[n/2]
Möbius ladder M_n n-1
pan
graph n-2
rook complement graph K_n square K_n^_ n
rook
graph K_n square K_n n
star
graph S_n 1
sun
graph [n/2]
sunlet
graph C_n circledot K_1 n
triangular
graph n-2
wheel
graph W_n 1
white
bishop graph WB_(n,n) n-1
See also
Connected Dominating Set, Dominance, Dominating Set, Domination Number, Domination Polynomial, Maximum Leaf Number, Minimum Connected Dominating SetExplore with Wolfram|Alpha
WolframAlpha
References
Sampathkumar, E.; and Walikar, H. B. "The Connected Domination Number of a Graph." J. Math. Phys. Sci. 13, 607-613, 1979.Referenced on Wolfram|Alpha
Connected Domination NumberCite this as:
Weisstein, Eric W. "Connected Domination Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConnectedDominationNumber.html