The independence polynomial of graph \(G\) is the function \(i(G, x) = \sum i_k x^k\), where \(i_k\) is the number of independent sets of cardinality \(k\) in \(G\). We ask the following question: for fixed independence number \(\beta\), how large can the modulus of a root of \(i(G, x)\) be, as a function of \(n\), the number of vertices? We show that the answer is \((\frac{n}{\beta})^{\beta – 1} + O(n^{S-2})\).
Citation
J. I. Brown, R. J. Nowakowski. Bounding the Roots of Independence Polynomials[J], Ars Combinatoria, Volume 058. 113-120. .