Domination Polynomial

 

Let  be the number of dominating sets of size  in a graph , then the domination polynomial  of  in the variable  is defined as

where  is the (lower) domination number of  (Kotek et al. 2012, Alikhani and Peng 2014).

 is multiplicative over connected components (Alikhani and Peng 2014).

Precomputed dominations polynomials for many named graphs in terms of a variable  and in the Wolfram Language as GraphData[graph, "DominationPolynomial"][x].

The following table summarizes closed forms for the domination polynomials of some common classes of graphs (cf. Alikhani and Peng 2014).

graph
barbell graph
book graph
cocktail party graph
complete bipartite graph
complete graph
empty graph
helm graph
sunlet graph

The following table summarizes the recurrence relations for domination polynomials for some simple classes of graphs.

graph	order	recurrence
antiprism graph	5
barbell graph	3
book graph	3
cocktail party graph	3
complete graph	2
cycle graph	3
empty graph	1
gear graph	6
helm graph	2
ladder graph	5
path graph	3
star graph	2
sun graph	2
sunlet graph	1
web graph	3
wheel graph	4

---

REFERENCES

Alikhani, S. and Peng, Y.-H. "Dominating Sets and Domination Polynomial of Cycles." Global J. Pure Appl. Math. 4, No. 2, 2008.

Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.

Kotek, T.; Preen, J.; Simon, F.; Tittmann, P; and Trinks, M. "Recurrence Relations and Splitting Formulas for the Domination Polynomial." Electron. J. Combin. 19, No. 3, Paper 47, 27 pp., 2012.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p47.

اخر الاخبار

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

قسم التطوير يقيم دورة عن أخلاقيات المهنة للمنتسبين الجدد

تتضمن زيارة المراقد المقدسة في كربلاء.. معهد القرآن الكريم النسوي ينظم سفرة دينية لطالباته

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

قسم الشؤون الفكرية يطلق فعاليات الأسبوع الثالث من برنامج البذرة الصالحة

المزيد

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

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ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