The characteristic polynomial of a generalized join graph

摘要

For a graph G with adjacency matrix A(G) and degree-diagonal matrix D(G), Cvetković et al introduced a bivariate polynomial ϕG(x,t)=det(xI−(A(G)−tD(G))), where I is the identity matrix. The polynomial ϕG(x, t) not only generalizes the characteristic polynomials of some well-known matrices related to G, such as the adjacency, the Laplacian matrices, but also has an elegant combinatorial interpretation as being equivalent to the Bartholdi zeta function. Let G=H[G1,G2,…,Gk] be the generalized join graph of G1,G2,…,Gk determined by graph H. In this paper, we first give a decomposition formula for ϕG(x, t). The decomposition formula provides us a new method to construct infinitely many pairs of non-regular ϕ-cospectral graphs. Then, as applications, explicit expressions for ϕG(x, t) of some special kinds of graphs are given.