Completion of Laplacian integral graphs via edge addition Original Research Article

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists of integers. We define and characterize the integrally completable graphs—those Laplacian integral graphs with the property that one can add in a sequence of edges, preserve Laplacian integrality with each addition, and continue the process until the complete graph has been constructed. We then discuss the integrally completable graphs with the property that the deletion of any edge yields a graph that is not integrally completable, and the graphs G having the property that for any graph H on the same number of vertices having G as a subgraph, H is necessarily Laplacian integral. Finally, we characterize the integrally completable graphs having distinct eigenvalues.