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 | |
| 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
Fingerprint
Dive into the research topics of 'The roots of the independence polynomial of a clawfree graph'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver