The roots of the independence polynomial of a clawfree graph

• Autores: Maria Chudnovsky, Paul D. Seymour
• Localización: Journal of combinatorial theory. Series B, ISSN 0095-8956, Vol. 97, Nº. 3, 2007, págs. 350-357
• Idioma: inglés
• DOI: 10.1016/j.jctb.2006.06.001
• Texto completo no disponible (Saber más ...)
• Resumen

  • The independence polynomial of a graph G is the polynomial ?Ax|A|, summed over all independent subsets AV(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].