On restricted edge-connectivity of vertex-transitive multigraphs

摘要

Let G = (V, E) be a multigraph. The multigraph G is called maximally edge-connected if λ(G) = δ(G), and super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivity λ'(G) of G is the minimum number of edges whose removal disconnects G into non-trivial components. If λ'(G) achieves the upper bound of restricted edge-connectivity, then G is said to be λ'-optimal. This work characterizes maximally edge-connected vertex-transitive multigraphs, super edge-connected vertex-transitive multigraphs, and λ'-optimal vertex-transitive multigraphs.