2
$\begingroup$

I know very little about graphs. I believe the following should be trivial, but I couldn't find an argument to prove it. Let $\Gamma$ be an undirected, connected, vertex-transitive graph on $n$ vertices.

  1. What is known about an upper bound for $d(\Gamma)$ the diameter of $\Gamma$? It seems that the worst case scenario is when $\Gamma$ is a cycle and then $d(\Gamma)=\lfloor n/2\rfloor$, is that true? What is known if it is not a cycle?

  2. Is it true that any two vertices in $\Gamma$ can be connected by two non-intersecting paths, that is, any two vertices are contained in a cycle? (That will show of course that $d(\Gamma) \leq n/2$.)

$\endgroup$
4
$\begingroup$

The answer to the second question is yes. A vertex-transitive connected finite graph (with more than two vertices) is $2$-connected, i.e., it can't be disconnected by removing a vertex. In a $2$-connected graph every pair of vertices lies on a cycle; this is a special case of Menger's theorem.

$\endgroup$
  • $\begingroup$ Can you explain why it is 2-connected? $\endgroup$ – Yiftach Barnea Apr 26 '18 at 6:02
  • 1
    $\begingroup$ If $G$ can be disconnected by removing a vertex, then by vertex transitivity every vertex has that property. But any connected finite graph $G$ (with more than two vertices) has at least two vertices $u,v$ such that $G-u$ and $G-v$ are connected. Namely, choose $u$ and $v$ so that $d(u,v)=\operatorname{diam}(G).$ $\endgroup$ – bof Apr 26 '18 at 7:55
4
$\begingroup$

The cycle has the greatest diameter. Apart from the cycle, the greatest diameter is close to $n/4$. For example consider a circular ladder consisting of two cycles of length $n/2$ connected by $n/2$ rungs. Or, break that one at some place and join it again a twist (like a Möbius strip). And there are a few more cases too. The exact list of connected transitive graphs with largest diameter other than a cycle depends on $n\;\mathrm{mod}\; 4$.

$\endgroup$
  • $\begingroup$ This is a bit disappointing I was hoping for a non-linear bound. $\endgroup$ – Yiftach Barnea Apr 26 '18 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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