The characteristic polynomial of a generalized join graph
Abstract For a graph G with adjacency matrix A(G) and degree-diagonal matrix D(G), Cvetkovic et al introduced a bivariate polynomial ϕ G ( x , t ) = d e t ( x I − ( A ( G ) − t D ( 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 [ G 1 , G 2 , … , G k ] be the generalized join graph of G 1 , G 2 , … , G k 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.