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 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 ceiling function. The parameters are positive integers.

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 graph{1 for n=1; 2 for n>=2
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){undefined for n=1; 2 for n>=2
complete bipartite graph K_(m,n){1 for min(m,n)=1; 2 otherwise
complete bipartite graph K_(n,n){1 for n=1; 2 for 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){1 for n=1; 2 for n>=2
2n-crossed prism graph2n
crown graph K_(n,n)-M{undefined for n=1,2; 4 for n>=3
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^_{1 for n=1; undefined for n=2; 3 for n>=3
rook graph K_n square K_nn
star graph S_n1
sun graph[n/2]
sunlet graph C_n circledot K_1n
triangular graph{1 for n=2; n-2 for n>=3
web graphn
wheel graph W_n1

See also

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

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.

Referenced on Wolfram|Alpha

Connected Domination Number

Cite this as:

Weisstein, Eric W. "Connected Domination Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConnectedDominationNumber.html

Subject classifications