Disjoint unions of complete graphs characterized by their Laplacian spectrum

Abstract

A disjoint union of complete graphs is in general not determined by its Laplacian
spectrum. It is shown in this paper that if one only considers the family of graphs without isolated vertex, then a disjoint union of complete graphs is determined by its Laplacian spectrum within this family. Moreover, it is shown that the disjoint union of two complete graphs with a and b vertices, a/b > 5/3 and b >1 is determined by its Laplacian spectrum. A counter-example is given when a/b = 5/3 .