Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture

Details Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture

2003-09-08

arxiv.org/abs/math/0309151v1

Mathematics

Combinatorics

10 pages, 2 figures

Scientific paper

A graph $G$ is well-covered if all its maximal stable sets have the same size, denoted by alpha(G) (M. D. Plummer, 1970). 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). J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that I(G;x) is unimodal (that is, there exists an index $k$ such that the part of the sequence of coefficients from the first to $k$-th is non-decreasing while the other part of coefficients is non-increasing) for any well-covered graph $G$. T. S. Michael and W. N. Traves (2002) proved that this assertion is true for alpha(G) < 4, while for alpha(G) from the set {4,5,6,7} they provided counterexamples. In this paper we show that for any integer $alpha$ > 7, there exists a (dis)connected well-covered graph $G$ with $alpha$ = alpha(G), whose independence polynomial is not unimodal. In addition, we present a number of sufficient conditions for a graph $G$ with alpha(G) < 7 to have unimodal independence polynomial.

Affiliated with

Also associated with

No associations

Rating

Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture 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 Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-47866