On Unimodality of Independence Polynomials of some Well-Covered Trees

Details On Unimodality of Independence Polynomials of some Well-Covered Trees On Unimodality of Independence Polynomials of some Well-Covered Trees

2002-11-03

arxiv.org/abs/math/0211036v1

Mathematics

Combinatorics

A preliminary version of this paper was presented at Second Haifa Workshop on Interdisciplinary Applications, of Graph Theory,

Scientific paper

The number of stable sets of cardinality $k$ in graph $G$ is the $k$-th coefficient of the independence polynomial of $G$ (I. Gutman and F. Harary, 1983). In 1990, Y. O. Hamidoune proved that for any claw-free graph, its independence polynomial is unimodal, i.e., there exists a coefficient $k$ such that the part of the sequence of coefficients from the first to $k$-th is non-decreasing while the second part of coefficients is non-increasing. Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erd\"{o}s (1987) asked whether for trees (or perhaps forests) the independence polynomial is unimodal. J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that it is true for any well-covered graph (a graph whose all maximal independent sets have the same size). V. E. Levit and E. Mandrescu (1999) demonstrated that every well-covered tree can be obtained as a join of a number of well-covered spiders, where a spider is a tree having at most one vertex of degree at least three. In this paper we show that the independence polynomial of any well-covered spider is unimodal. In addition, we introduce some graph transformations respecting independence polynomials. They allow us to reduce several types of well-covered trees to claw-free graphs, and, consequently, to prove that their independence polynomials are unimodal.

Affiliated with

Also associated with

No associations

Rating

On Unimodality of Independence Polynomials of some Well-Covered Trees 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 Unimodality of Independence Polynomials of some Well-Covered Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Unimodality of Independence Polynomials of some Well-Covered Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-590270