Domination Polynomial
المؤلف:
Alikhani, S. and Peng, Y.-H.
المصدر:
"Dominating Sets and Domination Polynomial of Cycles." Global J. Pure Appl. Math. 4, No. 2, 2008.
الجزء والصفحة:
...
15-3-2022
3248
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 |
![[-1+(1+x)^n]^2](https://mathworld.wolfram.com/images/equations/DominationPolynomial/Inline12.svg) |
book graph  |
![-2x^n+x^2(1+x)^((2n))+[x(2+x)]^n(1+2x)](https://mathworld.wolfram.com/images/equations/DominationPolynomial/Inline14.svg) |
cocktail party graph  |
 |
complete bipartite graph  |
![[(x+1)^m-1][(1+x)^n-1]+x^m+x^n](https://mathworld.wolfram.com/images/equations/DominationPolynomial/Inline18.svg) |
complete graph  |
 |
empty graph  |
 |
| helm graph |
![x^n[(x+1)(x+2)^n-1]](https://mathworld.wolfram.com/images/equations/DominationPolynomial/Inline23.svg) |
sunlet graph  |
![[x(x+2)]^n](https://mathworld.wolfram.com/images/equations/DominationPolynomial/Inline25.svg) |
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
