palindromic independence polynomials – a short survey
Colloquium in Mathematics and Computer Science on
palindromic independence polynomials – a short survey
palindromic independence polynomials – a short survey
Joint work with Vadim E. Levit, Ariel University
Sunday, April 26 | 15:00 | Science Building 8, Room 424
An independent set in a graph is a set of pairwise non-adjacent vertices, and α(G) is the size of a maximum independent set in the graph G. The independence polynomial of a graph G is the function I(G;x)= s₀+s₁x+...+sα xα, α = α(G), where sk denotes the number of independent sets of cardinality k in G. The independence polynomial was introduced by I. Gutman and F. Harary (1983) as a generalization of the matching polynomial.
Both polynomials are known to supply a substantial amount of information about the graph. Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots; can be non-log-concave, or even non-unimodal. J. W. Kennedy (Graph Theory Notes of New York, 1992) called a graph palindromic with respect to one of its polynomials (matching, characteristic), if the sequence of the polynomial coefficients is self-reciprocal. Recall that a sequence of real numbers (a₀,a₁,a₂,...,an) is said to be self-reciprocal if aj = an-j, j =0,1,..., Ln/2L.
In this talk, we survey the most important results referring palindromic independence polynomials. A number of conjectures and open problems are presented as well.
