Graphs with few distinct distance eigenvalues irrespective of the diameters

Abstract

The distance matrix of a simple connected graph $G$ is $D(G)=(d_{ij})$, where $d_{ij}$ is the distance between $i$th and $j$th vertices of $G$. The multiset of all eigenvalues of $D(G)$ is known as the distance spectrum of $G$. Lin et al.(On the distance spectrum of graphs. \newblock {\em Linear Algebra Appl.}, 439:1662-1669, 2013) asked for existence of graphs other than strongly regular graphs and some complete $k$-partite graphs having exactly three distinct distance eigenvalues. In this paper some classes of graphs with arbitrary diameter and satisfying this property is constructed. For each $k\in \{4,5,\ldots,11\}$ families of graphs that contain graphs of each diameter grater than $k-1$ is constructed with the property that the distance matrix of each graph in the families has exactly $k$ distinct eigenvalues. While making these constructions we have found the full distance spectrum of square of even cycles, square of hypercubes, corona of a transmission regular graph with $K_2$, and strong product of an arbitrary graph with $K_n$