Saeid Alikhani, Nasrin Jafari

DOI Number
First page
Last page


Let $G = (V, E)$ be a simple graph of order $n$. A  total dominating set of $G$ is a subset $D$ of $V$, such that every vertex of $V$ is adjacent to at least one vertex in  $D$. The total domination number of $G$ is  minimum cardinality of  total dominating set in $G$ and is denoted by $\gamma_t(G)$. The total domination polynomial of $G$ is the polynomial $D_t(G,x)=\sum_{i=\gamma_t(G)}^n d_t(G,i)$, where $d_t(G,i)$ is the number of total dominating sets of $G$ of size $i$. In this paper, we study roots of the total domination polynomial of some graphs.  We show that  all roots of $D_t(G, x)$ lie in the circle with center $(-1, 0)$ and radius $\sqrt[\delta]{2^n-1}$, where $\delta$ is the minimum degree of $G$. As a consequence, we prove that if $\delta\geq \frac{2n}{3}$,  then every integer root of $D_t(G, x)$ lies in the set $\{-3,-2,-1,0\}$.


graph; total domination number; total domination polynomial; root.

Full Text:



S. Akbari and S. Alikhani and Y. H. Peng: Characterization of graphs using domination polynomials. Eur. J. Combin. 31 (2010), 1714–1724.

S. Alikhani and N. Jafari: Some new results on the total domination polynomial of a graph. Ars Combin. In press. Available at http://arxiv.org/abs/1705.00826.

W. G. Bridges and R. A. Mena: Multiplicative cones- a family of three eigenvalue graph. Aequationes Math. 22 (1981), 208–214.

J. I. Brown and J. Tufts: On the roots of domination polynomials. Graphs Combin. 30 (2014), 527–547.

J. I. Brown and C. A. Hickmanand R. J. Nowakowski: On the location of roots of independence polynomials. J. Algebraic Combin. 19 (2004), 273–282.

E. R. Van Dam: Regular graphs with four eigenvalues. Linear Algebra Appl, 226/228 (1995), 139–162.

E. R. Van Dam: Graphs with few eigenvalues, An Interplay between Combinatorics and Algebra, Center Dissertation Series 20, Thesis, Tilburg University, 1996.

E. R. Van Dam: Nonregular graphs with three eigenvalues. J. Combin. Theory Ser, B 73 (1998), 101–118.

E. R. Van Dam and W. H. Haemers: Which graphs are determined by their spectrum?. Linear Algebra Appl, 373 (2003), 241–272.

M. Dod: The total domination polynomial and its generalization. In: Congressus Numerantium, 219 (2014), 207–226.

C. D. Godsil: Algebraic Combinatorics. Chapmanand Hall, NewYork. 1993.

F. Harary: On the group of the composition of two graphs. Duke Math. J.26 (1959), 29–36.

F. Harary: Graph Theory. Addison-Wesley, Reading, MA (1969).

O. J. Heilmann and E. H. Lieb: Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232.

M. A. Henning and A. Yeo: Total domination in graphs . Springer Monographs in Mathematics, 2013.

N. Jafari and S. Alikhani: On the roots of total domination polynomial of graphs, J. Discrete Math. Sci. Crypt., https://doi.org/10.1080/09720529.2019.1616908.

M. Klin and M. Muzychuk: On graphs with three eigenvalues. Discrete Math. 189 (1998), 191–207.

H. Chuang and G. R. Omidi: Graphs with three distinct eigenvalues and largest eigenvalue less than 8. Linear Algebra Appl. 430 (2009), 2053–2062.

Z. Ryjᡠcek and I. Schiermeyer: The flower conjecture in special classes of graphs. Discuss. Math. Graph Theory, 15 (1995), 179–184.

M. R. Oboudi: On the roots of domination polynomial of graphs. Discrete Appl. Math. 205 (2016), 126–131.

DOI: https://doi.org/10.22190/FUMI1904659A


  • There are currently no refbacks.

© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)