4
$\begingroup$

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann., 1971) that a connected vertex-transitive graph without $K_4$ has optimal vertex connectivity. My question is: which of the two papers by Mader mentioned above proves this result, and what is the exact statement of this result?

This result implies that all connected vertex-transitive graphs with clique number 2 or 3 have optimal vertex connectivity. In particular, all connected Cayley graphs generated by transpositions (these graphs are bipartite) have optimal vertex connectivity.

$\endgroup$
7
$\begingroup$

This article by Maya Stein states the relevant results on these two papers by Mader (page 11):

Which degree at each vertex do we need in order to ensure that our graph has a $k$-(edge-) connected subgraph?

It is known that in finite graphs a degree of $k$ is enough, and moreover the subgraph will be the graph itself. In fact, every finite vertex-transitive $k$-regular connected graph is $k$-edge-connected [27]. It is even k-connected, as long as it does not contain $K^4$ as a subgraph [25].

  • [25] W. Mader. Uber den Zusammenhang symmetrischer Graphen. Archiv der Math., 21:331-336, 1970.

  • [27] W. Mader. Minimale n-fach zusammenhangende Graphen. Math. Ann., 191:21-28, 1971.

So the result you're looking for is on the 1970 paper.

$\endgroup$
  • $\begingroup$ I think "nite" should be "finite"? Perhaps the ligature did not survive the cut-n-paste process? $\endgroup$ – Gordon Royle Nov 2 '15 at 23:37
  • $\begingroup$ @GordonRoyle Thanks! Just a copy-paste gone wrong. $\endgroup$ – Myshkin Nov 3 '15 at 0:05
  • $\begingroup$ @Myshkin. Thanks. I would appreciate if someone could confirm first-hand (from Mader's original paper) that this result is in Mader's paper. $\endgroup$ – Ashwin Ganesan Nov 3 '15 at 9:33
  • 1
    $\begingroup$ @AshwinGanesan Indeed, the 1970 paper states this as a theorem: "Satz 4. Wenn ein zusammenhängender eckensymmetrischer Graph vom Grad $g$ keinen $V_4$ enthält, ist er $g$-fach zusammenhängend." — "Theorem 4. If a connected vertex transitive graph of regularity $g$ contains no $K_4$, then it is $g$-connected." $\endgroup$ – M. Vinay Nov 17 '15 at 2:13

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.