A family of graphs whose independence polynomials are both palindromic and unimodal


Vadim E. LevitEugen Mândrescu


Abstract

carpathian_2007_23_108_116_abstract

Full PDF

carpathian_2007_23_108_116

A stable (or independent) set in a graph is a set of pairwise non-adjacent vertices. The stability number α(G) is the size of a maximum stable set in the graph G. The independence polynomial of G is defined by I(G; x) = s0 + s1x + s2x 2 + … + sαx α, α = α(G), where sk equals the number of stable sets of cardinality k in G (I. Gutman and F. Harary, 1983). In this paper, we build a family of graphs whose independence polynomials are palindromic and unimodal. We conjecture that all these polynomials are also log-concave.

Additional Information

Author(s)

Levit, Vadim E., Mândrescu, Eugen