On the distance spectra of central vertex join and central edge join of two regular graphs (Q6601214)

The distance matrix \(D(G)\) of a graph \(G\) is the square matrix with rows and columns indexed by vertices and entries given by the graph distance of the corresponding vertex pair. The distance Laplacian \(D^L(G)\) derives from \(D(G)\) in the same way that the Laplacian does from the adjacency matrix \(A(G)\): off-diagonal entries are negated, and suitable diagonal entries added to make all row and column sums vanish. As with the adjacency and the Laplacian matrix, it is natural to ask about the spectrum of the distance matrix and the distance Laplacian.\N\NThis article relates these spectra for graphs constructed using the so-called central graph to the eigenvalues of the adjacency matrix of the original graph. The central graph \(C(G)\) of a graph \(G\) is obtained by replacing each edge of \(G\) with a path of length \(2\), and each non-edge of \(G\) with an edge. If \(G\) is triangle-free we have \(\operatorname{diam}(C(G))\leq 3\), and \(D(C(G))\) may be straightforwardly expressed in terms of \(A(G)\), the incidence matrix of \(G\) and the adjacency matrix of its line graph (which in turn may be written in terms of the incidence matrix). If \(G\) is also \(k\)-regular, the authors give the eigenvalues of the distance matrix of \(C(G)\) in terms of those of the adjacency matrix \(A(G)\) of \(G\), the degree \(k\) and number of vertices \(n\). For each eigenvalue of \(A(G)\), other than the Perron-Frobenius eigenvalue \(k\), there are two eigenvalues of \(D(G)\) arising from suitable combinations of an eigenvector for \(A(G)\) together with its product with the incidence matrix. There are additionally two exceptional eigenvalues and \(-1\) with some multiplicity.\N\NSimilar results are proved for the spectrum of \(D^L(C(G))\), again under the assumption that \(G\) is \(k\)-regular and triangle free, and the spectra of the distance matrices and distance Laplacian for two types of joins involving the central graph. Both of these are obtained from a disjoint union of \(C(G_1)\) and \(G_2\) by adding edges between them: in one case all edges from \(V(G_1)\) to \(V(G_2)\) are added, and in the other case all edges from \(V(C(G_1))\setminus V(G_1)\) to \(V(G_2)\) are added. In both cases, this gives a graph with constant diameter, and the spectra are given on the assumption that \(G_1\) is triangle-free and \(k_1\) regular and \(G_2\) is \(k_2\)-regular (but may have triangles).