12
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ For your parenthetical subquestion, it appears to me that this condition is the same the graph's radius equaling its diameter. $\endgroup$ May 12, 2011 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$ May 12, 2011 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$ May 12, 2011 at 12:43

3 Answers 3

5
$\begingroup$

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

$\endgroup$
6
  • $\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$ May 12, 2011 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$ May 12, 2011 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$ May 12, 2011 at 7:45
  • $\begingroup$ @ Gerhard: Indeed it seems to work. Thanks! $\endgroup$ May 12, 2011 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$ May 12, 2011 at 15:50
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @ Roland: I keep the accepted answer on Gerhard, as he found the counter-example, but I really liked your input! Thanks! $\endgroup$ May 13, 2011 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$ May 14, 2011 at 5:42
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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