TY - JOUR
T1 - Very well-covered graphs with log-concave independence polynomials
AU - Levit, Vadim E.
AU - Mâ ndrescu, Eugen
PY - 2004
Y1 - 2004
N2 - If sk equals the number of stable sets of cardinality k in the graph G, then I(G; x) = σα (G) k=0 skxk is the independence polynomial of G (Gutman and Harary, 1983). Alavi, Malde, Schwenk and Erdös (1987) conjectured that I(G; x) is unimodal whenever G is a forest, while Brown, Dilcher and Nowakowski (2000) conjectured that I(G; x) is unimodal for any well- covered graph G. Michael and Traves (2002) showed that the assertion is false for well-covered graphs with (G) ≤ 4, while for very well-covered graphs the conjecture is still open. In this paper we give support to both conjectures by demonstrating that if α(G) ≤ 3, or G {K1,n, Pn : n ≥ 1}, then I(G* x) is log-concave, and, hence, unimodal (where G* is the very well-covered graph obtained from G by appending a single pendant edge to each vertex).
AB - If sk equals the number of stable sets of cardinality k in the graph G, then I(G; x) = σα (G) k=0 skxk is the independence polynomial of G (Gutman and Harary, 1983). Alavi, Malde, Schwenk and Erdös (1987) conjectured that I(G; x) is unimodal whenever G is a forest, while Brown, Dilcher and Nowakowski (2000) conjectured that I(G; x) is unimodal for any well- covered graph G. Michael and Traves (2002) showed that the assertion is false for well-covered graphs with (G) ≤ 4, while for very well-covered graphs the conjecture is still open. In this paper we give support to both conjectures by demonstrating that if α(G) ≤ 3, or G {K1,n, Pn : n ≥ 1}, then I(G* x) is log-concave, and, hence, unimodal (where G* is the very well-covered graph obtained from G by appending a single pendant edge to each vertex).
KW - Claw-free graph
KW - Independence polynomial
KW - Log-concavity
KW - Stable set
KW - Tree
KW - Unimodality
KW - Well-covered graph
UR - http://www.scopus.com/inward/record.url?scp=72049130896&partnerID=8YFLogxK
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:72049130896
SN - 1584-2851
VL - 20
SP - 73
EP - 80
JO - Carpathian Journal of Mathematics
JF - Carpathian Journal of Mathematics
IS - 1
ER -