TY - JOUR

T1 - The roots of the independence polynomial of a clawfree graph

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information:
E-mail addresses: [email protected] (M. Chudnovsky), [email protected] (P. Seymour). 1 This research was conducted during the period the author served as a Clay Mathematics Institute Research Fellow. 2 Partially supported by ONR Grant N00014-01-1-0608, and NSF Grant DMS-0070912.

PY - 2007/5

Y1 - 2007/5

N2 - The independence polynomial of a graph G is the polynomial ∑A x| A |, summed over all independent subsets A ⊆ V (G). We prove that if G is clawfree, then all the roots of its independence polynomial are real. This extends a theorem of Heilmann and Lieb [O.J. Heilmann, E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972) 190-232], answering a question posed by Hamidoune [Y.O. Hamidoune, On the numbers of independent k-sets in a clawfree graph, J. Combin. Theory Ser. B 50 (1990) 241-244] and Stanley [R.P. Stanley, Graph colorings and related symmetric functions: Ideas and applications, Discrete Math. 193 (1998) 267-286].

AB - The independence polynomial of a graph G is the polynomial ∑A x| A |, summed over all independent subsets A ⊆ V (G). We prove that if G is clawfree, then all the roots of its independence polynomial are real. This extends a theorem of Heilmann and Lieb [O.J. Heilmann, E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972) 190-232], answering a question posed by Hamidoune [Y.O. Hamidoune, On the numbers of independent k-sets in a clawfree graph, J. Combin. Theory Ser. B 50 (1990) 241-244] and Stanley [R.P. Stanley, Graph colorings and related symmetric functions: Ideas and applications, Discrete Math. 193 (1998) 267-286].

KW - Clawfree graphs

KW - Independence polynomial

KW - Roots

UR - http://www.scopus.com/inward/record.url?scp=33847650559&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847650559&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2006.06.001

DO - 10.1016/j.jctb.2006.06.001

M3 - Article

AN - SCOPUS:33847650559

SN - 0095-8956

VL - 97

SP - 350

EP - 357

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 3

ER -