Very well-covered graphs and the unimodality conjecture

Details Very well-covered graphs and the unimodality conjecture Very well-covered graphs and the unimodality conjecture

2004-06-30

arxiv.org/abs/math/0406623v1

Mathematics

Combinatorics

10 pages, 4 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 the graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). Let $a$ be the size of a maximum stable set. Alavi, Malde, Schwenk and Erdos (1987)conjectured that I(T,x) is unimodal for any tree T, while, in general, they proved that for any permutation $p$ of {1,2,...,a} there is a graph such that s_{p(1)}=...>=s_{a-1}>=s_{a} are valid for any (a) bipartite graph $G$; (b) quasi-regularizable graph $G$ on $2a$ vertices. In particular, we infer that this is true for (a) trees, thus doing a step in an attempt to prove Alavi et al.' conjecture; (b) very well-covered graphs. Consequently, for this case, the unconstrained subsequence appearing in the roller-coaster conjecture can be shorten to (s_{a/2},s_{a/2+1},...,s_{(2a-1)/3}). We also show that the independence polynomial of a very well-covered graph $G$ is unimodal for a<10, and is log-concave whenever a<6.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597022