0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 25, 2013 at 15:19

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .