Integral graphs with distinct eigenvalues

Abstract

A graph is called integral whenever eigenvalues of its adjacency matrix are all integer. Connected graphs whose eigenvalues are distinct and main are called controllable graphs. In [Applicable Analysis and Discrete Mathematics, 5(2011), 165-175.] it is proved that the only controllable integral graph is the one-vertex graph K1. The proof of the latter result depends highly on the classification of integral graphs with at most 10 vertices, which in turn depends on computer computations. Here we give a machine-free proof for a slight generalization of the latter result: The only integral graphs whose eigenvalues are all distinct are K1, K2 and the disjoint union of K2 and K1. © 2018 Charles Babbage Research Centre. All rights reserved.