The Generalized Characteristic Polynomial of the Km,n-Complement of a Bipartite Graph

The generalized matrix of a graph G is defined as M(G) = A(G) − tD(G) (t ∈ R, A(G) and D(G) respectively denote the adjacency matrix and the degree matrix of G), and the generalized characteristic polynomial of G is merely the characteristic polynomial of M(G). Let Km,n be the complete bipartite graph. Then the Km,n-complement of a subgraph G in Km,n is defined as the graph obtained by removing all edges of an isomorphic copy of G from Km,n. In this paper, by using a determinant expansion on the sum of two matrices (one of which is a diagonal matrix), a general method for computing the generalized characteristic polynomial of the Km,n-complement of a bipartite subgraph G was provided. Furthermore, when G is a graph with rank no more than 4, the explicit formula for the generalized characteristic polynomial of the Km,n-complements of G is given.