×

zbMATH — the first resource for mathematics

On the zeros of domination polynomial of a graph. (English) Zbl 1232.05098
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 109-115 (2010).
Summary: The domination polynomial of a graph \(G\) of order \(n\) is the polynomial \[ D(G, x)=\sum^n_{i=1} d(G,i)\,x^i, \] where \(d(G,i)\) is the number of dominating sets of \(G\) of size \(i\). Every root of \(D(G,x)\) is called a domination root of \(G\). In this paper, we completely determine the domination roots of all graphs with exactly three distinct domination roots. Also, we show that for every forest \(F\), \(D(F,-1)=(-1)^{\alpha(F)}\), where \(\alpha(F)\) is the independence number of \(F\).
For the entire collection see [Zbl 1202.05003].

MSC:
05C31 Graph polynomials
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite