Partial unimodality for independence polynomials of Konig-Egervary graphs

摘要

The stability number α(G) of the graph G is the size of a maximum stable set in G. If α(G) + μ(G) = |V(G)|, then G is called a Koenig-Egervary graph, where μ(G) is the matching number of G. If s_k denotes the number of stable sets of size k in G, then the polynomial I(G;x) having s_k as its coefficients, is called the independence polynomial of G (I. Gutman and F. Harary, 1983). Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erdoes (1987) conjectured that I(T, x) is unimodal for any tree T. In this paper we prove that s_([(2α-1)/3]) ≥····≥ s_(α-1) ≥ s_α are valid for any Koenig-Egervary graph. As a by-product, it gives a new proof of these inequalities for bipartite graphs. In particular, when trees are under investigation, the partial unimodality phenomenon we revealed may be considered as a step in an attempt to prove Alavi et al.' conjecture.