The roots of the independence polynomial of a clawfree graph

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2006.06.001

The roots of the independence polynomial of a clawfree graph

Maria Chudnovsky, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

138 Scopus citations

Abstract

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].

Original language	English (US)
Pages (from-to)	350-357
Number of pages	8
Journal	Journal of Combinatorial Theory. Series B
Volume	97
Issue number	3
DOIs	https://doi.org/10.1016/j.jctb.2006.06.001
State	Published - May 2007

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Clawfree graphs
Independence polynomial
Roots

Access to Document

10.1016/j.jctb.2006.06.001

Cite this

@article{c020c683de3448e987e9ab1549758b00,

title = "The roots of the independence polynomial of a clawfree graph",

abstract = "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].",

keywords = "Clawfree graphs, Independence polynomial, Roots",

author = "Maria Chudnovsky and Paul Seymour",

note = "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.",

year = "2007",

month = may,

doi = "10.1016/j.jctb.2006.06.001",

language = "English (US)",

volume = "97",

pages = "350--357",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "3",

}

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 -

The roots of the independence polynomial of a clawfree graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this