Super-edge-connected and OptimallySuper-edge-connected Bi-Cayley graphs

摘要

Let G be a finite group, S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G × {0,1} and edge set {{(g, 0), (gs,1)}, g ∈ G, s ∈ S}. A graph X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ' (X) of X is the minimum number of edges whose removal disconnects X into nontrivial components. A k-regular graph X is said to be optimally super-edge-connected if X is super-edge-connected and its restricted edge connectivity attains the maximum 2k-2. In this paper, we show that all connected Bi-Cayley graphs, except even cycles, are optimally super-edge-connected.