On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs

Details On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs

2003-05-15

arxiv.org/abs/math/0305227v1

Mathematics

Combinatorics

17 pages; 6 figures

Scientific paper

If for any k the k-th coefficient of a polynomial I(G;x)is equal to the number of stable sets of cardinality k in graph G, then it is called the independence polynomial of G (Gutman and Harary, 1983). A graph G is very well-covered (Favaron, 1982) if it has no isolated vertices, its order equals 2*alpha(G), where alpha(G) is the size of a maximum stable set, and it is well-covered (i.e., all its maximal independent sets are of the same size, Plummer, 1970). For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G*. Under certain conditions, any well-covered graph equals G* for some G (Finbow, Hartnell and Nowakowski, 1993). The root of the smallest modulus of the independence polynomial of any graph is real (Brown, Dilcher, and Nowakowski, 2000). 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) and I(G*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G*;x) different from -1, which appears as a root of multiplicity alpha(G*)- alpha(G) for I(G*;x). We also prove that the real roots of I(G*;x) are in [-1,-1/(2*alpha(G*)), while for a general graph of order n we show that its roots lie in |z| > 1/(2n-1). Using the properties of the roots of the independence polynomial, we demonstrate that the independence polynomial distinguishes well-covered spiders (well-covered trees with at most one vertex of degree greater than two) among general well-covered trees.

Affiliated with

Also associated with

No associations

Rating

On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Roots of Independence Polynomials of Almost All Very Well-Covered Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-520966