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$.)

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you explain why it is 2-connected? $\endgroup$
    – Yiftach Barnea
    Apr 26, 2018 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, 2018 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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is a bit disappointing I was hoping for a non-linear bound. $\endgroup$
    – Yiftach Barnea
    Apr 26, 2018 at 15:35

Your Answer

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

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