Unimodality of independence polynomials of the incidence product of graphs

Abstract

Given two graphs G and H, assume that V(G)={v1,v2,…,vn} and U is a subset of V(H). We introduce a new graph operation called the incidence product, denoted by G⊙HU, as follows: insert a new vertex into each edge of G, then join with edges those pairs of new vertices on adjacent edges of G. Finally, for every vertex vi∈V(G), replace it by a copy of the graph H and join every new vertex being adjacent to vi to every vertex of U. It generalizes the line graph operation. We prove that the independence polynomial IG⊙HU;x=In(H;x)MG;xI2(H−U;x)I2(H;x),where M(G;x) is its matching polynomial. Based on this formula, we show that the incidence product of some graphs preserves symmetry, unimodality, reality of zeros of independence polynomials. As applications, we obtain some graphs so-formed having symmetric and unimodal independence polynomials. In particular, the graph Q(G) introduced by Cvetković, Doob and Sachs has a symmetric and unimodal independence polynomial.

Locations

• Discrete Mathematics - View - PDF