Graphs with few distinct \(D\)-eigenvalues determined by their \(D\)-spectra (Q1979380)

The distance matrix \(D\) of a graph \(G\) with vertex set \(\{v_1,v_2,\ldots ,v_n\}\) is the \(n\times n\) matrix that has its \((i,j)\) position equal to the distance between the vertices \(v_i\) and \(v_j\). In this article, the author studies graphs whose distance matrix has at most three eigenvalues different than \(-1\) and \(-2\). He proves that if \(G\) is such a graph, then \(G\) can be obtained from either \(P_4\) or a connected graph \(H\) with at most \(3\) vertices, by replacing each vertex with either a clique or an independent set. If this is the case, then \(G\) is said to be a mixed extension of \(P_4\) or of \(H\). Furthermore, they characterized which graphs are determined by the spectrum of their distance matrix, and which are co-spectral. The main tools used are Cauchy's interlace theorem and the fact that if \(G\) is a mixed extension of \(H\), then the eigenvalues of \(G\) can be obtained from an \(|H|\times |H|\) matrix.