Journal of the Iranian Mathematical Society

Journal of the Iranian Mathematical Society

On the domination roots of friendship graphs and book graphs

Document Type : Research Article

Authors
1 Department of Computer Science‎, ‎Shahid Bahonar University of Kerman‎, ‎Kerman‎, ‎Iran.
2 Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran.
Abstract
The domination polynomial of a graph $G$ of order $n$ is $D(G,x)=\sum_{i=1}^{n} d(G,i) x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. For the friendship graph $F_n$, which is the join of $K_1$ with $nK_2$, the domination polynomial is known to be $D(F_n,x)=(2x+x^2)^n+x(1+x)^{2n}$. Motivated by proposed open problems in [S. Alikhani, J.I. Brown, S. Jahari, On the domination polynomials of friendship graphs, Filomat 30:1 (2016), 169-178], we prove that for every even positive integer $n$, $D(F_n,x)$ has exactly three real roots: $x=0$, one root in $(-2,-1)$, and one root in $(-1,0)$. Second, we establish an asymptotic upper bound on the modulus of the complex domination roots of $F_n$: for any root $x$ of $D(F_n,x)$ and for sufficiently large $n$, we have $|x| \leq \sqrt{2n/\ln n} + 1$, so that $|x| = O\left(\sqrt{n/\ln n}\right)$. Furthermore, we address the domination roots of the book graph $B_n$, obtained by gluing $n$ copies of $C_4$ along a common edge. We describe the limiting curve of the roots of $D(B_n,x)$ as $n\to\infty$ and provide an asymptotic bound on their moduli. These results provide a deeper understanding of the nature of domination roots for these important families of graphs.
Keywords
Subjects

[1] S. Akbari, S. Alikhani and Y. H. Peng, Characterization of graphs using domination polynomial, European J. Combin. 31 (2010), no. 7, 17141724.
[2] S. Alikhani, The domination polynomial of a graph at 1, Graphs Combin. 29 (2013), no. 5, 11751181.
[3] S. Alikhani, Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin. 114 (2014) 257266.
[4] S. Alikhani, J. I. Brown and S. Jahari, On the domination polynomials of friendship graphs, Filomat 30 (2016), no. 1, 169178.
[5] J. I. Brown and J. Tufts, On the roots of domination polynomials, Graphs Combin. 30 (2014), no. 3, 527547.
[6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W .H. Freeman, New York, 1979.
[7] A. N. Ghameshlou, A. J. Rad and M. Mohammadi, A note on the domination entropy of graphs, J. Disc. Math. Appl. 10 (2025) 1120.
[8] T. Kotek, J. Preen and P. Tittmann, Subset-sum representations of domination polynomials, Graphs Combin. 30 (2014), no. 3, 647660.
Volume 7, Issue 1
This issue is in progress but all papers are fully citable
February 2026
Pages 43-51