R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl. 278 (1998), 221-236. Math Reviews 99i:05141.

If G is a graph, its Laplacian is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. (See, e.g., publication 93.) The main thrust of the present article is to establish several Laplacian eigenvector "principles" that, in certain cases, can be used to deduce the effect on the Laplacian spectrum of contracting, adding, or deleting edges, and/or contracting vertices. An application is given to the construction of isospectral graphs.

If V = {1,2,3,4,5,6} and E = {1-2, 2-3, 2-5, 3-4, 3-6, 4-5, 5-6}, then H = (V,E) is a bipartite graph whose degree sequence is d(H) = (3,3,3,2,2,1), and whose Laplacian characteristic polynomial is p(x) = x(x-2)(x-3)^2(x^2-6x+4). Overlooked during the preparation of this article is that G = H^c, the complement of H, is a nonbipartite graph, with degree sequence (4,2,2,2,2,2), that is isospectral with H, i.e., the Laplacian characteristic polynomial of G is also p(x) (given above). Because H and its complement are both connected, neither is decomposable.

Among the publications citing this article are: