Connected Domination Number
المؤلف:
Sampathkumar, E.; and Walikar, H. B
المصدر:
"The Connected Domination Number of a Graph." J. Math. Phys. Sci. 13
الجزء والصفحة:
607-613
15-3-2022
2341
Connected Domination Number
The connected domination number of a connected graph 
, denoted 
, is the size of a minimum connected dominating set of a graph 
.
The maximum leaf number 
and connected domination number of a graph 
are connected by
where 
is the vertex count of 
.
Many families of graphs have simple closed forms, as summarized in the following table. In the table, 
denotes the floor function.
| graph family |
connected domination number |
| Andrásfai graph |
![<span style=]() {1 for n=1; 3 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline9.svg" style="height:61px; width:123px" /> |
| Apollonian network |
![<span style=]() {1 for n=1,2; 1/2(3^(n-3)+5) otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline10.svg" style="height:65px; width:258px" /> |
| antiprism graph |
 |
| barbell graph |
2 |
black bishop graph  |
![<span style=]() {1 for n=1,2; n-2 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline13.svg" style="height:61px; width:188px" /> |
book graph  |
2 |
cocktail party graph  |
2 |
complete bipartite graph  |
![<span style=]() {1 for min(m,n)=1; 2 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline17.svg" style="height:61px; width:219px" /> |
complete bipartite graph  |
2 |
complete graph  |
1 |
complete tripartite graph  |
![<span style=]() {1 for min(k,m,n)=1; 2 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline21.svg" style="height:61px; width:250px" /> |
complete tripartite graph  |
2 |
 -crossed prism graph |
 |
crown graph  |
4 |
cycle graph  |
 |
| gear graph |
![1+[n/2]](https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline28.svg) |
| helm graph |
 |
ladder graph  |
![<span style=]() {2 for n=3; n otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline31.svg" style="height:61px; width:123px" /> |
Möbius ladder  |
 |
| pan graph |
 |
path graph  |
![<span style=]() {1 for n=1,2; n-2 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline36.svg" style="height:61px; width:188px" /> |
prism graph  |
![<span style=]() {2 for n=3; n otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline38.svg" style="height:61px; width:123px" /> |
rook complement graph  |
 |
rook graph  |
 |
star graph  |
1 |
| sun graph |
![[n/2]](https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline44.svg) |
sunlet graph  |
 |
| triangular graph |
 |
| web graph |
 |
wheel graph  |
1 |
white bishop graph  |
 |
REFERENCES
Sampathkumar, E.; and Walikar, H. B. "The Connected Domination Number of a Graph." J. Math. Phys. Sci. 13, 607-613, 1979.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
