Bounding the roots of independence polynomials. (Q2716005)

For a simple and finite graph \(G\), in the independence polynomial \(i(G,x)=\sum _{k=0}^{\beta } i_kx^k\) the coefficient \(i_k\) is the number of independent sets of size \(k\) and \(\beta \) is the independence number of \(G\). The authors prove, by means of the Eneström-Kakeya theorem, that the maximum modulus of a root of \(i(G,x)\), where \(G\) has order \(n\), is \((n/(\beta -1))^{\beta -1}+O(n^{\beta -2})\). They show that for line graphs of trees the maximum modulus is at most \(\binom {\beta }{2}\). The authors conclude by saying that a similar bound (with \(f(\beta )\) in place of \(\binom {\beta }{2}\)) can be proved for line graphs in general.