Lexicographic polynomials of graphs and their spectra

Abstract

For a (simple) graph H and non-negative integers c0; c1; ... ; cd (cd ≠ 0), p(H) =Σkd=0 ck . Hk is the lexicographic polynomial in H of degree d, where the sum of two graphs is their join and ck . Hk is the join of ck copies of Hk. The graph Hk is the kth power of H with respect to the lexicographic product (H0 = K1). The spectrum (if H is connected and regular) and the Laplacian spectrum (in general case) of p(H) are determined in terms of the spectrum of H and ck's. Constructions of infinite families of cospectral or integral graphs are announced.