3
$\begingroup$

Let $\Gamma$ be a finite connected bipartite $k$-regular multigraph (for $k\ge 3$) which is both vertex and edge transitive. Here by regularity I mean every vertex has $k$ edges incident to it. By multigraph I mean a graph with possibly multiple edges between any two given vertices. I do not allow loops.

If $\Gamma$ is simple then the vertex-transitivity implies that $\Gamma$ is $k$-edge connected. Clearly removing all the $k$ edges adjacent to a vertex will disconnect the graph. Is it possible to disconnect the graph by removing $k$ edges without isolating a vertex?

To be clear, I want to show that the only way to disconnect such a graph by removing $k$ edges must involve isolating a vertex.

(Edited to add bipartite and remove $k$ edges condition)

$\endgroup$
5
  • $\begingroup$ The cube graph $Q_3$ is a finite bipartite $3$-regular graph which is both vertex and edge transitive. Can you disconnect it by removing $3$ edges without isolating a vertex? $\endgroup$
    – bof
    Jul 16, 2022 at 20:22
  • $\begingroup$ @bof Surely not? $\endgroup$
    – Brandon du Preez
    Jul 16, 2022 at 20:28
  • 1
    $\begingroup$ @BrandonduPreez Right, so that was my counterexample to the OP's question, which seemed to be asking whether every such graph can be disconnected in such a way. I guess I misread the question. $\endgroup$
    – bof
    Jul 16, 2022 at 20:36
  • $\begingroup$ @bof Re-reading it myself it's not obvious whether OP wants to know if this is ever possible or always possible. $\endgroup$
    – Brandon du Preez
    Jul 16, 2022 at 20:43
  • $\begingroup$ @BrandonduPreez I've added a line to make it more clear. $\endgroup$
    – stupid_question_bot
    Jul 17, 2022 at 15:58

1 Answer 1

Reset to default
2
$\begingroup$

Short answer: No, it is not possible.

Long answer involves some history.

The property you are looking for has a name: a graph is super-$\lambda$ if it is $\lambda$-edge-connected, and every edge cut with $\lambda$ edges leaves an isolated vertex.

So the result you want is this: Every connected edge and vertex transitive bipartite graph with vertex degree at least $3$ is super-$\lambda$. Apparently, R. Tindell proved that every connected edge-transitive graph with degree at least $3$ is super-$\lambda$ in the 1980s (according to his own citation to a paper in review), but I cannot find this paper!

I found the citation and result (without proof) in "Circulants and their connectives" by R. Tindell and F. Boesch.

Luckily, the result has been improved (with an original proof that does not use the inaccessible one by Tindell). The fact that every edge-transitive connected graph that is not a cycle is super-$\lambda$ (i.e., the result we want) is an immediate consequence of Theorem 1 in the paper "Super Edge Connectivity Properties of Connected Edge Symmetric Graphs" by Qiaoliang Li and Qiao Li - published in the journal Networks volume 33, issue 2.

The proof is a bit involved, and the paper itself can be found online.

$\endgroup$
5
  • $\begingroup$ I'm looking at this paper again, and it's unclear if they allow multiple edges in their graphs. For example, for Proposition 4 they cite a paper of Watkins, which only considers simple graphs (if I'm not mistaken this means no multiple edges). Do you have any feeling whether the result should be true when you allow multiple edges? $\endgroup$
    – stupid_question_bot
    Jul 20, 2022 at 15:30
  • $\begingroup$ @stupid_question_bot Not sure. My intuition is that an edge and vertex transitive graph with multi-edges must be very simple, or just a "multi-edge thickening" of a vertex and edge-transitive graph. I'm not sure how you define an automorphism of a multi-graph, but if it must send a "pack of $k$ parallel edges" to another "pack of $k$ parallel edges" then this is certainly the case. $\endgroup$
    – Brandon du Preez
    Jul 20, 2022 at 18:33
  • $\begingroup$ That's a good point, I'll have to think about it more. $\endgroup$
    – stupid_question_bot
    Jul 20, 2022 at 21:37
  • $\begingroup$ By the way, would you happen to know of a reference for the statement that a connected edge-transitive (simple) graph should have edge connectivity equal to the minimum vertex degree? In the paper by Li-Li that you cite, this is Proposition 4, but they cite Watkins, which seems to prove the result for vertex-connectedness, not edge-connectedness. This makes me suspicious of the results of Li-Li... $\endgroup$
    – stupid_question_bot
    Jul 20, 2022 at 21:39
  • $\begingroup$ @stupid_question_bot I'm afraid I do not. I tried to find the result online, but was quite surprised to see little mention of it. $\endgroup$
    – Brandon du Preez
    Jul 21, 2022 at 9:23

You must log in to answer this question.

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