Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-11T21:04:02.610Z Has data issue: false hasContentIssue false
  • English
  • Français

Note on the Smallest Root of the Independence Polynomial

Published online by Cambridge University Press:  18 July 2012

PÉTER CSIKVÁRI
PÉTER CSIKVÁRI*
Affiliation:
Department of Computer Science, Eötvös Loránd University, H-1117 Budapest, Pázmány Péter sétány 1/C, Hungary and Alfréd Rényi Institute of Mathematics, H-1053 Budapest, Reáltanoda u. 13-15, Hungary (e-mail: csiki@cs.elte.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

One can define the independence polynomial of a graph G as follows. Let ik(G) denote the number of independent sets of size k of G, where i0(G)=1. Then the independence polynomial of G is I(G,x)=∑k=0n(−1)kik(G)xk. In this paper we give a new proof of the fact that the root of I(G,x) having the smallest modulus is unique and is real.

Keywords

Primary 05C31
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 1 , January 2013 , pp. 1 - 8
Copyright
Copyright © Cambridge University Press 2012

References

[1]Cartier, P. and Foata, D. (1969) Problèmes Combinatoires de Commutation et Rèarrangements, Vol. 85 of Lecture Notes in Mathematics, Springer.Google Scholar
[2]Fisher, D. C. (1989) The number of words of length n in a free ‘semi-Abelian’ monoid. Amer. Math. Monthly 96 610–614.CrossRefGoogle Scholar
[3]Fisher, D. C. (1989) Lower bounds on the number of triangles in a graph. J. Graph Theory 13 505–512.Google Scholar
[4]Fisher, D. C. and Ryan, J. (1992) Bounds on the largest root of the matching polynomial. Discrete Math. 110 275–278.Google Scholar
[5]Fisher, D. C. and Solow, A. E. (1990) Dependence polynomials. Discrete Math. 82 251–258.Google Scholar
[6]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[7]Goldwurm, M. and Santini, M. (2000) Clique polynomials have a unique root of smallest modulus. Inform. Process. Lett. 75 127–132.Google Scholar
[8]Hajiabolhassan, H. and Mehrabadi, M. L. (1998) On clique polynomials. Austral. J. Combin. 18 313–316.Google Scholar
[9]Levit, V. E. and Mandrescu, E. (2005) The independence polynomial of a graph – a survey. In Proc. 1st International Conference on Algebraic Informatics: Thessaloniki 2005 (Bozapalidis, S., Kalampakas, A. and Rahonis, G., eds), Aristotle University of Thessaloniki, pp. 233–254.Google Scholar
[10]Nikiforov, V. (2011) The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 1599–1618.Google Scholar
[11]Razborov, A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603–618.Google Scholar
[12]Reiher, C. The clique density theorem. Preprint.Google Scholar
[13]Scott, A. D. and Sokal, A. D. (2005) The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma. J. Statist. Phys. 118 1151–1261.CrossRefGoogle Scholar
[14]Scott, A. D. and Sokal, A. D. (2006) On dependency graphs and the lattice gas. Combin. Probab. Comput. 15 253–279.Google Scholar