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

Abstract

Let \(G\) be a finite group, \(S\) (possibly, contains the identity element) be a subset of \(G\). The Bi-Cayley graph \(\text{BC}(G, S)\) is a bipartite graph with vertex set \(G \times \{0,1\}\) and edge set \(\{\{(g,0), (gs,1)\}, g \in G, s \in 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 \(\lambda'(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.