# Graphs with circulant distance matrices

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?

-
Other cyclic like graphs work, e.g. the complete graph, as well as complements of such graphs. Gerhard "Ask Me About System Design" Paseman, 2013.01.25 –  Gerhard Paseman Jan 25 '13 at 15:19

## 1 Answer

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.

-