Roots of Independence Polynomials of Well Covered Graphs
J.I. Brown
, K. Dilcher
and R.J. Nowakowski
DOI: 10.1023/A:1008705614290
Abstract
Let G be a well covered graph, that is, all maximal independent sets of G have the same cardinality, and let i k denote the number of independent sets of cardinality k in G. We investigate the roots of the independence polynomial i(G, x) = 
i kx k. In particular, we show that if G is a well covered graph with independence number 
, then all the roots of i(G, x) lie in in the disk |z| 
(this is far from true if the condition of being well covered is omitted). Moreover, there is a family of well covered graphs (for each ) for which the independence polynomials have a root arbitrarily close to - .
i kx k. In particular, we show that if G is a well covered graph with independence number , then all the roots of i(G, x) lie in in the disk |z| (this is far from true if the condition of being well covered is omitted). Moreover, there is a family of well covered graphs (for each ) for which the independence polynomials have a root arbitrarily close to - .Pages: 197–210
Keywords: graph; independence; polynomial; root; well covered
Full Text: PDF
References
1. M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions, National Bureau of Standards, Washington, D.C., 1964.
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. N. Anderson, E.B. Saff, and R.S. Varga, “On the Enestr\ddot om-Kakeya theorem and its sharpness,” Lin. Alg. Appl. 28 (1979), 5-16.
4. E.J. Barbeau, Polynomials, Springer-Verlag, New York, 1989.
5. J.I. Brown and C.J. Colbourn, “Roots of the reliability polynomial,” SIAM J. Disc. Math. 5 (1992), 571- 585.
6. J.I. Brown and C.J. Colbourn, “On the log concavity of reliability and matroidal sequences,” Adv. Appl. Math. 15 (1994), 114-127.
7. G. Chartrand and L. Lesniak, Graphs and Digraphs, Wadsworth and Brooks/Cole, Monterey, 1986.
8. F.R.K. Chung, P.C. Fishburn, and R.L. Graham, “On unimodality for linear extensions of partial orders,” SIAM J. Alg. Disc. Meth. 1 (1980), 405-410.
9. L. Comtet, Advanced Combinatorics, Reidel Pub. Co., Boston, 1974.
10. D.C. Fisher, “Lower bounds on the number of triangles in a graph,” J. Graph Th. 13 (1989), 505-512.
11. D.C. Fisher and J. Ryan, “Bounds on the number of complete subgraphs,” Disc. Math. 103 (1992), 313-320.
12. D.C. Fisher and A.E. Solow, “Dependence Polynomials,” Disc. Math. 82 (1990), 251-258.
13. C. Godsil, “Real graph polynomials,” Progress in Graph Theory, Academic Press, Toronto, 1984, pp. 281- 293.
14. C.D. Godsil and I. Gutman, “On the theory of matching polynomials,” J. Graph Theory 5 (1981), 137- 144.
15. I. Gutman, “An identity for the independence polynomials of trees,” Publ. Inst. Math. (Beograd) (N.S.) 50 (1991), 19-23.
16. I. Gutman, “Independent vertex sets in some compound graphs,” Publ. Inst. Math. (Beograd) (N.S.) 66 (1992), 5-9.
17. I. Gutman, “Some analytic properties of the independence and matching polynomials,” Match 28 (1992), 139-150.
18. I. Gutman and F. Harary, “Generalizations of the matching polynomial,” Utilitas Math. 24 (1983), 97-106.
19. Y.O. Hamidoune, “On the number of independent k-sets in a claw free graph,” J. Combin. Theory B 50 (1990), 241-244.
20. E.R. Hansen, A Table of Series and Products, Prentice-Hall, Englewood Cliffs, N.J., 1975.
21. C. Hoede and X. Li, “Clique polynomials and independent set polynomials of graphs,” Discrete Math. 125 (1994), 219-228.
22. A. Hurwitz, “ \ddot Uber die Wurzeln einiger transcendenter Gleichungen,” Mitteilungen Math. Ges. Hamburg 2 (1890), 25-31. Also in Mathematische Werke, Band 1, Birk\ddot auser Verlag, Basel, 1962, pp. 299-305.
23. C. Mahoney, “On the unimodality of the independent set numbers of a class of matroids,” J. Combin. Theory Ser. B 39 (1985), 77-85. BROWN, DILCHER AND NOWAKOWSKI
24. M. Marden, Geometry of Polynomials, 2nd edition, American Mathematical Society, Providence, 1966.
25. J.H. Mason, “Matroids: unimodal conjectures and Motzkin's theorem,” in Combinatorics, D.J.A. Welsh and D.R. Woodall (Eds.), London Math Soc., London, 1972, pp. 207-221.
26. S. Negami and K. Ota, “Polynomial invariants of graphs II,” Graphs and Combin. 12 (1996), 189-198.
27. M.D. Plummer, “Some covering concepts in graphs,” J. Combin. Theory 8 (1970), 91-98.
28. M.D. Plummer, “Well-covered graphs: a survey,” Quaestiones Math. 8 (1993), 91-98.
29. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, L.W. Beineke and R.J. Wilson (Eds.), Academic Press, New York, 1988, pp. 15-42.
30. R.P. Stanley, “Two combinatorial applications of the Aleksandrov-Fenchel inequalities,” J. Combin. Theory Ser. A 31 (1981), 56-65.
31. D.J.A. Welsh, “Combinatorial problems in matroid theory,” Combinatorial Mathematics and its Applications, Academic Press, New York, 1971, pp. 291-307.
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. N. Anderson, E.B. Saff, and R.S. Varga, “On the Enestr\ddot om-Kakeya theorem and its sharpness,” Lin. Alg. Appl. 28 (1979), 5-16.
4. E.J. Barbeau, Polynomials, Springer-Verlag, New York, 1989.
5. J.I. Brown and C.J. Colbourn, “Roots of the reliability polynomial,” SIAM J. Disc. Math. 5 (1992), 571- 585.
6. J.I. Brown and C.J. Colbourn, “On the log concavity of reliability and matroidal sequences,” Adv. Appl. Math. 15 (1994), 114-127.
7. G. Chartrand and L. Lesniak, Graphs and Digraphs, Wadsworth and Brooks/Cole, Monterey, 1986.
8. F.R.K. Chung, P.C. Fishburn, and R.L. Graham, “On unimodality for linear extensions of partial orders,” SIAM J. Alg. Disc. Meth. 1 (1980), 405-410.
9. L. Comtet, Advanced Combinatorics, Reidel Pub. Co., Boston, 1974.
10. D.C. Fisher, “Lower bounds on the number of triangles in a graph,” J. Graph Th. 13 (1989), 505-512.
11. D.C. Fisher and J. Ryan, “Bounds on the number of complete subgraphs,” Disc. Math. 103 (1992), 313-320.
12. D.C. Fisher and A.E. Solow, “Dependence Polynomials,” Disc. Math. 82 (1990), 251-258.
13. C. Godsil, “Real graph polynomials,” Progress in Graph Theory, Academic Press, Toronto, 1984, pp. 281- 293.
14. C.D. Godsil and I. Gutman, “On the theory of matching polynomials,” J. Graph Theory 5 (1981), 137- 144.
15. I. Gutman, “An identity for the independence polynomials of trees,” Publ. Inst. Math. (Beograd) (N.S.) 50 (1991), 19-23.
16. I. Gutman, “Independent vertex sets in some compound graphs,” Publ. Inst. Math. (Beograd) (N.S.) 66 (1992), 5-9.
17. I. Gutman, “Some analytic properties of the independence and matching polynomials,” Match 28 (1992), 139-150.
18. I. Gutman and F. Harary, “Generalizations of the matching polynomial,” Utilitas Math. 24 (1983), 97-106.
19. Y.O. Hamidoune, “On the number of independent k-sets in a claw free graph,” J. Combin. Theory B 50 (1990), 241-244.
20. E.R. Hansen, A Table of Series and Products, Prentice-Hall, Englewood Cliffs, N.J., 1975.
21. C. Hoede and X. Li, “Clique polynomials and independent set polynomials of graphs,” Discrete Math. 125 (1994), 219-228.
22. A. Hurwitz, “ \ddot Uber die Wurzeln einiger transcendenter Gleichungen,” Mitteilungen Math. Ges. Hamburg 2 (1890), 25-31. Also in Mathematische Werke, Band 1, Birk\ddot auser Verlag, Basel, 1962, pp. 299-305.
23. C. Mahoney, “On the unimodality of the independent set numbers of a class of matroids,” J. Combin. Theory Ser. B 39 (1985), 77-85. BROWN, DILCHER AND NOWAKOWSKI
24. M. Marden, Geometry of Polynomials, 2nd edition, American Mathematical Society, Providence, 1966.
25. J.H. Mason, “Matroids: unimodal conjectures and Motzkin's theorem,” in Combinatorics, D.J.A. Welsh and D.R. Woodall (Eds.), London Math Soc., London, 1972, pp. 207-221.
26. S. Negami and K. Ota, “Polynomial invariants of graphs II,” Graphs and Combin. 12 (1996), 189-198.
27. M.D. Plummer, “Some covering concepts in graphs,” J. Combin. Theory 8 (1970), 91-98.
28. M.D. Plummer, “Well-covered graphs: a survey,” Quaestiones Math. 8 (1993), 91-98.
29. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, L.W. Beineke and R.J. Wilson (Eds.), Academic Press, New York, 1988, pp. 15-42.
30. R.P. Stanley, “Two combinatorial applications of the Aleksandrov-Fenchel inequalities,” J. Combin. Theory Ser. A 31 (1981), 56-65.
31. D.J.A. Welsh, “Combinatorial problems in matroid theory,” Combinatorial Mathematics and its Applications, Academic Press, New York, 1971, pp. 291-307.