This question is related to [Realizing the diameter of a finite regular graph](https://mathoverflow.net/questions/64695/realizing-the-diameter-of-a-finite-regular-graph)


Let $X=(V,E)$ be a finite, connected, regular graph of diameter $D$. Assume that, for every vertex $x\in V$, there exists some vertex $y\in V$ such that $d(x,y)=D$ (btw, does this property has a name in the literature?)


Question: does there exist a permutation $\alpha$ of $V$ such that $d(x,\alpha(x))=D$ for every $x\in V$?


Note that $\alpha$ is NOT required to be a graph automorphism.


Example: let $G$ be a finite group, and let $X$ be a Cayley graph of $G$ wrt some symmetric generating set $S$; use right multiplications by generators to define $X$, so that the distance $d$ is left-invariant. Let $g$ be any element of maximal word length in $G$. Then $\alpha(x)=xg$ (right multiplication by $g$) does the job in the question.



"Antipodal" maps on regular graphs?
I don't know. The following is a near miss which might be useful. 


Start with a hexagonal cycle path ABCDEFA. Duplicate point C to C' and connect C' to
B,C, and D. Similarly duplicate points E and F, and add edges EE', FF', and the 3 edges
to form the path DE'F'A. Then it has diameter 3, but the only point that is distance 3 from E (and also from E') is B, so it cannot accommodate such a permutation. The only problem is that vertex D has degree 4, so the graph is just shy of being 3-regular.


It may be possible to use this by stitching together two large even cycles to get
a regular graph (with the property that two vertices must share an antipode), but I will let someone else do it.


**EDIT 2011.05.12**
Thanks to Alain, Aaron, and Roland for their encouragement and checking, I will bring
the comment's example into this answer. Indeed two 12-cycles can be stitched together,
say at vertices 3 and 4, and at 6 and 7, and at 10 and 11, with 6 vertices and edges added to form 3 separate ladders as in the example above. This time the graph is 3-regular, and
points 1 and 1' have 7 as the unique common antipode, as do also 9 and 9' share vertex 3 as an antipode. The result has 27 edges, 18 vertices, and diameter 6, and does not admit a permutation that takes every vertex to one at distance 6 from that vertex, because e.g. there are not enough antipodes for 9 and 9' to share in such a permutation. 


The "ladders" in the construction can be replaced by graphs which have something like a complete graph on k vertices at each rung (instead of the complete graph on two vertices as in the present example) to get examples with arbitrarily high regularity and in which k vertices share an antipode.
**END EDIT 2011.05.12**


Gerhard "Cycles Can Make Me Dizzy" Paseman, 2011.05.11


