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	{1 for n=1; 3 otherwise" src="https://mathworld.wolfram.com/images/equations/ConnectedDominationNumber/Inline9.svg" style="height:61px; width:123px" />
Apollonian network	{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	{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	{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	{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
helm graph
ladder graph	{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	{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	{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
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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تعلن أسماء الفائزين بمسابقة الذكرى الميمونة لولادة الإمام الحسين (عليه السلام)

شعبة الخطابة النسوية تستعد لإطلاق مسابقة (سبيل المنتظرين) بنسختها الثالثة

قسم الشؤون الفكرية يقدّم محاضرتين توعويتين لطلبة جامعة المنارة في ميسان

سماحة السيد الصافي يؤكّد أن القرآن عظّم شخصية النبي (صلّى الله عليه وآله) وكشف زيف ما أُلصِق بسيرته

المزيد

الآخبار الصحية

دراسة: محاولة متعمدة لنشر الإنفلونزا تنتهي بـ"مفاجأة"

من خبير في هارفارد.. 6 نصائح يومية "فعالة" لإبطاء الشيخوخة

7 مشروبات طبيعية لتقوية الذاكرة وزيادة التركيز

عرض شائع على الأصابع.. قد يكشف سرطان الرئة مبكرا

المزيد

الآخبار التكنلوجية

وسائل التواصل بين الإفراط والامتناع.. ما هو الحد الآمن للمراهقين؟

أعمق خندق في الكوكب الارض !

روساتوم: روسيا تقترب من تطوير ساعات ذرية فائقة الدقة

مفاجأة علمية عن الإنجاب.. كم طفلا يطيل عمر المرأة؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength