On the Location of Roots of Independence Polynomials
J.I. Brown
, C.A. Hickman2
and R.J. Nowakowski2
2ddagger
DOI: 10.1023/B:JACO.0000030703.39946.70
Abstract
The independence polynomial of a graph G is the function i( G, x) = 
k 
0 i k x k, where i k is the number of independent sets of vertices in G of cardinality k. We prove that real roots of independence polynomials are dense in (- 
, 0], while complex roots are dense in 
, even when restricting to well covered or comparability graphs. Throughout, we exploit the fact that independence polynomials are essentially closed under graph composition.
k 0 i k x k, where i k is the number of independent sets of vertices in G of cardinality k. We prove that real roots of independence polynomials are dense in (- , 0], while complex roots are dense in , even when restricting to well covered or comparability graphs. Throughout, we exploit the fact that independence polynomials are essentially closed under graph composition.Pages: 273–282
Keywords: graph; independence; polynomial; roots
Full Text: PDF
References
1. L. Ahlfors, Complex Analysis, 3rd edition, McGraw-Hill, New York, 1979.
2. Y. Alavi, P. Malde, A.J. Schwenk, and P. Erd\ddot os, “The vertex independence sequence of a graph is not constrained,” Congr. Numer. 58 (1987), 15-23.
3. S. Beraha, J. Kahane, and N. Weiss, “Limits of zeros of recursively defined families of polynomials,” in Studies in Foundations and Combinatorics: Advances in Math., Supplementary Studies, vol. 1, G. Rota (Ed.), Academic Press, New York, 1978.
4. S. Beraha, J. Kahane, and N.J. Weiss, “Limits of chromatic zeros of some families of graphs,” J. Combin. Theory Ser. B 28 (1980), 52-65.
5. N.L. Biggs, R.M. Damerell, and D.A. Sands, “Recursive families of graphs,” J. Combin. Theory Ser. B 12 (1972), 123-131.
6. J.I. Brown, K. Dilcher, and R.J. Nowakowski, “Roots of independence polynomials of well covered graphs,” J. Algebraic Combin. 11 (2000), 197-210.
7. J.I. Brown and C.A. Hickman, “On chromatic roots of large subdivisions of graphs,” Discrete Math. 242 (2002), 17-30.
8. L. Comtet, Advanced Combinatorics, Reidel Pub. Co., Boston, 1974.
9. D.C. Fisher, “Lower bounds on the number of triangles in a graph,” J. Graph Theory 13 (1989), 505-512.
10. D.C. Fisher and A.E. Solow, “Dependence polynomials,” Discrete Math. 82 (1990), 251-258.
11. D.C. Fisher and J. Ryan, “Bounds on the number of complete subgraphs,” Discrete Math. 103 (1992), 313- 320.
12. C.D. Godsil, “Real graph polynomials,” in Progress in Graph Theory, J.A. Bondy and U.S.R. Murty (Eds.), Academic Press, Toronto, 1984.
13. C.D. Godsil and I. Gutman, “On the theory of matching polynomials,” J. Graph Theory, 5 (1981), 137-144.
14. I. Gutman, “On independent vertices and edges of belt graphs,” Publ. Inst. Math. (Belgrade) 59 (1996), 11-17.
15. I. Gutman, “Numbers of independent vertex and edge sets of a graph: Some analogies,” Graph Theory Notes (New York) 22 (1992), 18-22.
16. I. Gutman, “Some analytic properties of the independence and matching polynomials,” Match. 28 (1992), 139-150. BROWN, HICKMAN AND NOWAKOWSKI
17. I. Gutman, “An idendity for the independence polynomials of trees,” Publ. Inst. Math. (Belgrade) 50 (1991), 19-23.
18. I. Gutman, “On independent vertices and deges in a graph,” in Topics in Combinatorics and Graph Theory, R. Bodendeik and R. Henn (Eds.), Physica-Verlag, Heidelberg, 1990.
19. I. Gutman, “Graphs with maximimum and minimum independence numbers,” Publ. Inst. Math. (Belgrade) 34 (1983), 73-79.
20. Y.O. Hamidoune, “On the number of k-sets in a claw free graph,” J. Combin. Theory Ser. B 50 (1990), 241-244.
21. O.J. Heilmann and E.H. Lieb, “Theory of monomer-dimer systems,” Commun. Math. Phys. 25 (1972), 190- 232.
22. E. Hille, Analytic Function Theory, Ginn & Co., Boston, 1959.
23. C. Hoede and X. Li, “Clique polynomials and independent set polynomials of graphs,” Discrete Math. 25 (1994), 219-228.
24. B. Jackson, “A zero-free interval for the chromatic polynomials of graphs,” Combin. Probab. Comp. 2 (1993), 325-336.
25. L. Lovasz and M.D. Plummer, Matching Theory, North-Holland Publishing Co., Amsterdam, 1986.
26. M.D. Plummer, “Well covered graphs: A survey,” Quaestiones Math. 8 (1970), 91-98.
27. R.C. Read and G.F. Royle, “Chromatic roots of families of graphs,” in Graph Theory, Combinatorics, and Applications, Y. Alavi et al. (Eds.), Wiley, New York, 1991.
28. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, Y.W. Beineke and R.J. Wilson (Eds.), Academic Press, New York, 1988.
29. A.D. Sokal, “Chromatic polynomials, Potts models and all that,” Physica A 279 (2000), 324-332.
30. R.P. Stanley, “Log-concave and unimodal sequences in algebra, combinatorics, and geometry,” Ann. New York Acad. Sci. 576 (1989), 500-534.
31. C. Thomassen, “The zero-free intervals for chromatic polynomials of graphs,” Combin. Probab. Comp. 6 (1997), 4555-4564.
32. D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.
2. Y. Alavi, P. Malde, A.J. Schwenk, and P. Erd\ddot os, “The vertex independence sequence of a graph is not constrained,” Congr. Numer. 58 (1987), 15-23.
3. S. Beraha, J. Kahane, and N. Weiss, “Limits of zeros of recursively defined families of polynomials,” in Studies in Foundations and Combinatorics: Advances in Math., Supplementary Studies, vol. 1, G. Rota (Ed.), Academic Press, New York, 1978.
4. S. Beraha, J. Kahane, and N.J. Weiss, “Limits of chromatic zeros of some families of graphs,” J. Combin. Theory Ser. B 28 (1980), 52-65.
5. N.L. Biggs, R.M. Damerell, and D.A. Sands, “Recursive families of graphs,” J. Combin. Theory Ser. B 12 (1972), 123-131.
6. J.I. Brown, K. Dilcher, and R.J. Nowakowski, “Roots of independence polynomials of well covered graphs,” J. Algebraic Combin. 11 (2000), 197-210.
7. J.I. Brown and C.A. Hickman, “On chromatic roots of large subdivisions of graphs,” Discrete Math. 242 (2002), 17-30.
8. L. Comtet, Advanced Combinatorics, Reidel Pub. Co., Boston, 1974.
9. D.C. Fisher, “Lower bounds on the number of triangles in a graph,” J. Graph Theory 13 (1989), 505-512.
10. D.C. Fisher and A.E. Solow, “Dependence polynomials,” Discrete Math. 82 (1990), 251-258.
11. D.C. Fisher and J. Ryan, “Bounds on the number of complete subgraphs,” Discrete Math. 103 (1992), 313- 320.
12. C.D. Godsil, “Real graph polynomials,” in Progress in Graph Theory, J.A. Bondy and U.S.R. Murty (Eds.), Academic Press, Toronto, 1984.
13. C.D. Godsil and I. Gutman, “On the theory of matching polynomials,” J. Graph Theory, 5 (1981), 137-144.
14. I. Gutman, “On independent vertices and edges of belt graphs,” Publ. Inst. Math. (Belgrade) 59 (1996), 11-17.
15. I. Gutman, “Numbers of independent vertex and edge sets of a graph: Some analogies,” Graph Theory Notes (New York) 22 (1992), 18-22.
16. I. Gutman, “Some analytic properties of the independence and matching polynomials,” Match. 28 (1992), 139-150. BROWN, HICKMAN AND NOWAKOWSKI
17. I. Gutman, “An idendity for the independence polynomials of trees,” Publ. Inst. Math. (Belgrade) 50 (1991), 19-23.
18. I. Gutman, “On independent vertices and deges in a graph,” in Topics in Combinatorics and Graph Theory, R. Bodendeik and R. Henn (Eds.), Physica-Verlag, Heidelberg, 1990.
19. I. Gutman, “Graphs with maximimum and minimum independence numbers,” Publ. Inst. Math. (Belgrade) 34 (1983), 73-79.
20. Y.O. Hamidoune, “On the number of k-sets in a claw free graph,” J. Combin. Theory Ser. B 50 (1990), 241-244.
21. O.J. Heilmann and E.H. Lieb, “Theory of monomer-dimer systems,” Commun. Math. Phys. 25 (1972), 190- 232.
22. E. Hille, Analytic Function Theory, Ginn & Co., Boston, 1959.
23. C. Hoede and X. Li, “Clique polynomials and independent set polynomials of graphs,” Discrete Math. 25 (1994), 219-228.
24. B. Jackson, “A zero-free interval for the chromatic polynomials of graphs,” Combin. Probab. Comp. 2 (1993), 325-336.
25. L. Lovasz and M.D. Plummer, Matching Theory, North-Holland Publishing Co., Amsterdam, 1986.
26. M.D. Plummer, “Well covered graphs: A survey,” Quaestiones Math. 8 (1970), 91-98.
27. R.C. Read and G.F. Royle, “Chromatic roots of families of graphs,” in Graph Theory, Combinatorics, and Applications, Y. Alavi et al. (Eds.), Wiley, New York, 1991.
28. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, Y.W. Beineke and R.J. Wilson (Eds.), Academic Press, New York, 1988.
29. A.D. Sokal, “Chromatic polynomials, Potts models and all that,” Physica A 279 (2000), 324-332.
30. R.P. Stanley, “Log-concave and unimodal sequences in algebra, combinatorics, and geometry,” Ann. New York Acad. Sci. 576 (1989), 500-534.
31. C. Thomassen, “The zero-free intervals for chromatic polynomials of graphs,” Combin. Probab. Comp. 6 (1997), 4555-4564.
32. D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.