Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T14:22:12.716Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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