On restricted edge-connectivity of half-transitive multigraphs

Abstract

Let $G=(V,E)$ be a multigraph (it has multiple edges, but no loops). The edge connectivity, denoted by $\lambda (G)$, is the cardinality of a minimum edge-cut of $G$. We call $G$ maximally edge-connected if $\lambda (G)=\delta (G)$, and $G$ super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivity ${\lambda }^{\prime }(G)$ of $G$ is the minimum number of edges whose removal disconnects $G$ into non-trivial components. If ${\lambda }^{\prime }(G)$ achieves the upper bound of restricted edge-connectivity, then $G$ is said to be ${\lambda }^{\prime }$-optimal. A bipartite multigraph is said to be half-transitive if its automorphism group is transitive on the sets of its bipartition. In this paper, we will characterize maximally edge-connected half-transitive multigraphs, super edge-connected half-transitive multigraphs, and ${\lambda }^{\prime }$-optimal half-transitive multigraphs.