Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.