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.

  • 2
    $\begingroup$ For your parenthetical subquestion, it appears to me that this condition is the same the graph's radius equaling its diameter. $\endgroup$ – Clinton Conley May 12 '11 at 6:32
  • 1
    $\begingroup$ This question can be reformulated as follows: given a regular graph $A$ of diameter $D$ such that every vertex of $A$ is at distance $D$ from some other vertex, we construct a new graph $B$ with the same vertices as $A$ and with edges corresponding to vertices at distance $D$ in $A$. Can we always find a collection of disjoint edges and cycles in $B$ which contain all vertices? $\endgroup$ – Roland Bacher May 12 '11 at 8:36
  • $\begingroup$ The case $D=2$ is equivalent to question mathoverflow.net/questions/64770/…, motivated by my failure to find a small counterexample. $\endgroup$ – Roland Bacher May 12 '11 at 12:43

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

  • $\begingroup$ I call the subgraph BCC'D a ladder of length 1, and the subgraph DEE'FF'A a ladder of length 2. If one can connect short disjoint ladders of the right lengths by edges, one might get the desired 3-regular example. Gerhard "Needs Another Cup Of Coffee" Paseman, 2011.05.11 $\endgroup$ – Gerhard Paseman May 12 '11 at 6:46
  • 2
    $\begingroup$ Using ladders of lengths 3,2, and 1 (and 3 additional edges), I think a graph of diameter 6 which has 18 vertices and is 3 regular has more than one pair of points which share an antipode. So I say that the answer, in general, is no. Gerhard "Ask Me About System Design" Paseman, 2011.05.12 $\endgroup$ – Gerhard Paseman May 12 '11 at 7:38
  • 1
    $\begingroup$ I also think that replacing each rung of the ladder by a complete graph on k vertices (or something close) can allow you to adjust this example to get graphs of arbitrarily large regularity which will not admit the desired permutation because k vertices will map antipodally to a shared vertex. Gerhard "Ask Me About System Design" Paseman, 2011.05.12 $\endgroup$ – Gerhard Paseman May 12 '11 at 7:45
  • $\begingroup$ @ Gerhard: Indeed it seems to work. Thanks! $\endgroup$ – Alain Valette May 12 '11 at 15:35
  • $\begingroup$ Nice! Make it an answer. I think ladders of lengths 1,1,2 also works. Actually, length 2 plus one edge looks ok too (6 vertices 9 edges) $\endgroup$ – Aaron Meyerowitz May 12 '11 at 15:50

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.

  • $\begingroup$ @ Roland: I keep the accepted answer on Gerhard, as he found the counter-example, but I really liked your input! Thanks! $\endgroup$ – Alain Valette May 13 '11 at 11:15
  • $\begingroup$ Roland: also, one has to be careful to use short strings of fat beads, as otherwise one finds antipodes to some "fat" vertices among other "fat" vertices. I think ABCDef is something I dismissed early because d_1 was an antipode to b_0. With short ladders, one doesn't run into that problem. I too like the description and the alternate formulations though. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 $\endgroup$ – Gerhard Paseman May 14 '11 at 5:42

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$


Your Answer

