LAPLACIAN GRAPH EIGENVECTORS

If G is a graph, its Laplacian is the difference of the diagonal matri x of its vertex degrees and its adjacency matrix. The main thrust of t he present article is to prove several Laplacian eigenvector ''princip les'' which in certain cases can be used to deduce the effect on the s pectrum of contracting, adding or deleting edges and/or of coalescing vertices. One application is the construction of two isospectral graph s on 11 vertices having different degree sequences, only one of which is bipartite, and only one of which is decomposable. (C) 1998 Elsevier Science Inc. All rights reserved.