Question

The cycle has this property. For instance, the distance matrix for a 6-cycle is:

$A=\begin{bmatrix}
0 & 1 & 2 & 3 & 2 & 1 \\ 1 & 0 & 1 & 2 & 3 & 2 \\ 2 & 1 & 0 & 1 & 2 & 3 \\ 3 & 2 & 1 & 0 & 1 & 2 \\ 2 & 3 & 2 & 1 & 0 & 1 \\ 1 & 2 & 3 & 2 & 1 & 0 \\ \end{bmatrix}$

The question is: is the cycle the only graph with this property?

Answer 1

Any circulant graph has this property. A circulant graph is a graph that has an automorphism that's a cyclic permutation of its vertices. If you apply permute the rows and columns of the distance matrix with the same permutation, you must get the same matrix, so the distance matrix is a circulant matrix.

Graphs other than circulant graphs can't have this property, because the ones in the distance matrix determine the edges.