"Antipodal" maps on regular graphs? This question is related to 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.
 A: 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
A: Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary 
graph and apply the answer to question
Existence of a nice  subset of edges in $k-$regular simple graphs?.
It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.
More generally, the situation can be resumed as follows:
Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map
if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.
Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$,
we set 
$$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$
Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if 
$\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.
(This result follows easily from Kevin P. Costello answer to question Existence of a nice  subset of edges in $k-$regular simple graphs? .)
Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$.
This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)
Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$
of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching
$f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$
The marriage-condition in the Theorem is for example satisfied if the number
$\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of 
$v$. This is for instance the case if $G$ is a regular graph of diameter $2$.
Gerhard Paseman's examples of a regular graph violating the marriage-condition 
with $\mathcal A(v)$ never empty can be described as follows.
Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a
graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices
$i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.
The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.
Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated
to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering
the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$
is reduced to the unique vertex $e_0$.
Correction:
$ABCDef$ does not work for a stupid reason pointed out by Gerhard Paseman. Take $ABCdeFgh$ instead. Considering $S=\lbrace A_+,A_-\rbrace$, we have $\mathcal A(A_+,A_-)=e_0$ which violates the marriage condition.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
A: FOLLOW-UP to Roland Bacher's answer (too long for a comment!)
In the OP it was observed that Cayley graphs admit antipodal maps. This can be generalized as follows:
LEMMA: Finite, connected, vertex-transitive graphs admit antipodal maps.
Proof: For $S$ a finite subset of the vertex set of some graph $Y$, denote by $\Gamma(S)$ the set of vertices adjacent to at least one vertex of $S$. It is classical that, if $Y$ is a regular graph, then the inequality $|\Gamma(S)|\geq |S|$ holds (Recall the easy argument: assuming that $Y$ is $k$-regular, count in two ways the edges joining $S$ to $\Gamma(S)$; as edges emanating from $S$, there are $k|S|$ of them; as edges entering $\Gamma(S)$, there are at most $k|\Gamma(S)|$ of them).
Now, let $X=(V,E)$ be a finite, connected, vertex-transitive graph. Define the {\it antipodal graph} $X^a$ as the graph with vertex set $V$, with $x$ adjacent to $y$ whenever the distance between $x$ and $y$ in $X$, is equal to $diam(X)$. By vertex-transitivity of $X$, the graph $X^a$ is regular. Now observe that, for $S\subset V$, the set $\Gamma(S)$ in $X^a$ is exactly the set ${\cal A}(S)$ defined by Roland Bacher. By regularity of $X^a$ and the observation beginning the proof, we therefore have $|{\cal A}(S)|\geq|S|$ for every $S\subset V$, and Bacher's result applies. $\;\square$ 
