On Unimodality of Independence Polynomials of Some Well-Covered Trees

摘要

The stability number α(G) of the graph G is the size of a maximum stable set of G. If s_k denotes the number of stable sets of cardinality k in graph G, then I(G;x) = ∑ from k = 0 of α(G) to s_kx~k is the independence polynomial of G (I. Gutman and F. Harary 1983). In 1990, Y. O. Hamidoune proved that for any claw-free graph G (a graph having no induced subgraph isomorphic to K_(1,3)), I(G;x) is unimodal, i.e., there exists some k ∈ {0,1,…, α(G)} such that s_0 ≤s_1 ≤ … ≤ s_(k-1) ≤ s_k ≥ s_(k+1) ≥ … ≥ s_α(G). Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erdos (1987) asked whether for trees the independence polynomial is unimodal. J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that I (G;x) is unimodal for any well-covered graph G (a graph whose all maximal independent sets have the same size). Michael and Traves (2002) showed that this conjecture is true for well-covered graphs with α(G) ≤ 3, and provided counterexamples for α(G) ∈ {4,5,6,7}. In this paper we show that the nondependence polynomial of any well-covered spider is unimodal and locate its mode, where a spider is a tree having at most one vertex of degree at least three. In addition, we extend some graph transformations, first introduced in [14], 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.