On the roots of independence polynomials of almost all very well-covered graphs
If sk s k denotes the number of stable sets of cardinality k in graph G , and ?(G) ? ( G ) is the size of a maximum stable set, then I ( G ; x ) = ? k = 0 ? ( G ) s k x k is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97106]. A graph G is very well-covered  [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177187] if it has no isolated vertices, its order equals 2?(G) 2 ? ( G ) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 9198]. For instance, appending a single pendant edge to each vertex of G  yields a very well-covered graph, which we denote by G* G * . Under certain conditions, any well-covered graph equals G* G * for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 4468]. The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles. In this paper we establish formulae connecting the coefficients of I(G;x) I ( G ; x ) and I(G*;x) I ( G * ; x ) , which allow us to show that the number of roots of I(G;x) I ( G ; x ) is equal to the number of roots of I(G*;x) I ( G * ; x ) different from -1 - 1 , which appears as a root of multiplicity ?(G*)-?(G) ? ( G * ) - ? ( G ) for I(G*;x) I ( G * ; x ) . We also prove that the real roots of I(G*;x) I ( G * ; x ) are in [-1,-1/2?(G*)) [ - 1 ,- 1 / 2 ? ( G * ) ) , while for a general graph of order n  we show that its roots lie in |z|>1/(2n-1) | z | > 1 / ( 2 n - 1 ) . Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs ). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 8487] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders ( K 1 , n * , n ? 1 ) among well-covered trees.
05c69 05c05 (primary) 05e99 05a20 (secondary)