Abstract
A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is
where s k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).
Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.
In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alavi, Y., Malde, P.J., Schwenk, A.J., Erdös, P.: The vertex independence sequence of a graph is not constrained. Congr. Numer. 58, 15–23 (1987)
Arocha, J.L.: Propriedades del polinomio independiente de un grafo. Rev. Cienc. Mat. V, 103–110 (1984)
Brown, J.I., Dilcher, K., Nowakowski, R.J.: Roots of independence polynomials of well-covered graphs. J. Algebr. Combin. 11, 197–210 (2000)
Brown, J.I., Hickman, C.A., Nowakowski, R.J.: On the location of roots of independence polynomials. J. Algebr. Combin. 19, 273–282 (2004)
Brown, J.I., Nowakowski, R.J.: Bounding the roots of independence polynomials. Ars Combin. 58, 113–120 (2001)
Chudnovsky, M., Seymour, P.: The roots of the independence polynomial of a claw-free graph. J. Comb. Theory B 97, 350–357 (2007)
Favaron, O.: Very well-covered graphs. Discrete Math. 42, 177–187 (1982)
Finbow, A., Hartnell, B., Nowakowski, R.J.: A characterization of well-covered graphs of girth 5 or greater. J. Comb. Theory B 57, 44–68 (1993)
Fisher, D.C., Solow, A.E.: Dependence polynomials. Discrete Math. 82, 251–258 (1990)
Goldwurm, M., Santini, M.: Clique polynomials have a unique root of smallest modulus. Inf. Process. Lett. 75, 127–132 (2000)
Gutman, I., Harary, F.: Generalizations of the matching polynomial. Utilitas Math. 24, 97–106 (1983)
Gutman, I.: Independence vertex palindromic graphs. Graph Theory Notes N. Y. Acad. Sci. XXIII, 21–24 (1992)
Gutman, I.: A contibution to the study of palindromic graphs. Graph Theory Notes N. Y. Acad. Sci. XXIV, 51–56 (1993)
Gutman, I.: Independence vertex sets in some compound graphs. Publications de l’Institut Mathématique 52, 5–9 (1992)
Hajiabolhassan, H., Mehrabadi, M.L.: On clique polynomials. Australas. J. Comb. 18, 313–316 (1998)
Hamidoune, Y.O.: On the number of independent k-sets in a claw-free graph. J. Comb. Theory B 50, 241–244 (1990)
Hardy, G.H., Littlewood, J.E., Polya, G.: Inequalities. Cambridge University Press, Cambridge (1952)
Heilmann, O.J., Lieb, E.H.: Theory of monomer-dimer systems. Commun. Math. Phys. 25, 190–232 (1972)
Hoede, C., Li, X.: Clique polynomials and independent set polynomials of graphs. Discrete Math. 125, 219–228 (1994)
Kennedy, J.W.: Palindromic graphs. Graph Theory Notes of New York Academy of Sciences XXII, 27–32 (1992)
Levit, V.E., Mandrescu, E.: On well-covered trees with unimodal independence polynomials. Congr. Numerantium 159, 193–202 (2002)
Levit, V.E., Mandrescu, E.: On unimodality of independence polynomials of some well-covered trees. In: Calude, C.S. et al. (eds.). DMTCS 2003, LNCS, Vol. 2731, pp. 237–256. Springer (2003)
Levit, V.E., Mandrescu, E.: A family of well-covered graphs with unimodal independence polynomials. Congr. Numerantium 165, 195–207 (2003)
Levit, V.E., Mandrescu, E.: Very well-covered graphs with log-concave independence polynomials. Carpathian J. Math. 20, 73–80 (2004)
Levit, V.E., Mandrescu, E.: The independence polynomial of a graph—a survey. Proceedings of the 1st International Conference on Algebraic Informatics, Aristotle University of Thessaloniki, Greece, pp. 233–254 (2005). http://web.auth.gr/cai05/papers/20.pdf
Levit, V.E., Mandrescu, E.: Independence polynomials and the unimodality conjecture for very well-covered, quasi-regularizable, and perfect graphs. In: Bondy, A. et al. (eds.). Graph Theory in Paris, Proceedings of a Conference in Memory of Claude Berge, pp.243–254, Birhäauser Verlag, Basel (2007)
Levit, V.E., Mandrescu, E.: On the roots of independence polynomials of almost all very well-covered graphs. Discrete Appl. Math. 156, 478–491 (2008)
Matchett, P.: Operations on well-covered graphs and the Roller–Coaster Conjecture. Electr. J. Comb., 11, #45 (2004)
Plummer, M.D.: Some covering concepts in graphs. J. Comb. Theory 8, 91–98 (1970)
Plummer, M.D.: Well-covered graphs—a survey. Questiones Math. 16, 253–287 (1993)
Stanley, R.P.: Graph colorings and related symmetric functions: ideas and applications. Discrete Math. 193, 267–286 (1998)
Stanley, R.P.: Positivity problems and conjectures in algebraic combinatorics. Mathematics: frontiers and perspectives. American Mathematical Society, Providence, pp. 295–319 (2000)
Stevanović, D.: Graphs with palindromic independence polynomial. Graph Theory Notes of New York Academy of Sciences XXXIV, 31–36 (1998)
Zhu, Z.F.: The unimodality of independence polynomials of some graphs. Australas. J. Comb. 38, 27–34 (2007)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mandrescu, E. Building Graphs Whose Independence Polynomials Have Only Real Roots. Graphs and Combinatorics 25, 545–556 (2009). https://doi.org/10.1007/s00373-009-0857-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-009-0857-5