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
    Commented 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
    Commented 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
    Commented Apr 26, 2018 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .