TOPICS
Search

Connected Domination Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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 familyconnected domination number
Andrásfai graph{1 for n=1; 3 otherwise
Apollonian network{1 for n=1,2; 1/2(3^(n-3)+5) otherwise
antiprism graphn-1
barbell graph2
black bishop graph BB_(n,n){1 for n=1,2; n-2 otherwise
book graph S_(n+1) square P_22
cocktail party graph K_(n×2)2
complete bipartite graph K_(m,n){1 for min(m,n)=1; 2 otherwise
complete bipartite graph K_(n,n)2
complete graph K_n1
complete tripartite graph K_(k,m,n){1 for min(k,m,n)=1; 2 otherwise
complete tripartite graph K_(n,n,n)2
2n-crossed prism graph2n
crown graph K_2 square K_n^_4
cycle graph C_nn-2
gear graph1+[n/2]
helm graphn
ladder graph nP_2{2 for n=3; n otherwise
Möbius ladder M_nn-1
pan graphn-2
path graph P_n{1 for n=1,2; n-2 otherwise
prism graph Y_n{2 for n=3; n otherwise
rook complement graph K_n square K_n^_n
rook graph K_n square K_nn
star graph S_n1
sun graph[n/2]
sunlet graph C_n circledot K_1n
triangular graphn-2
web graphn
wheel graph W_n1
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 Domination Number

Explore with Wolfram|Alpha

References

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. https://mathworld.wolfram.com/ConnectedDominationNumber.html

Subject classifications