Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421399 | Discrete Applied Mathematics | 2008 | 14 Pages |
If sksk 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)skxk is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97–106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177–187] 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) 91–98]. 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) 44–68].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) 197–210]. 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/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219–228] 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) 84–87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders (K1,n*,n⩾1) among well-covered trees.