Connectivity Of Two Classes Of 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) of G with respect to S is defined as the bipartite graph with vertex set G × { 0,1} and edge set {(g, 0)(sg, 1) : g ∈ G,s ∈ S}. Clearly, the Bi-Cayley graph BC(G,S) is a |S|-regular graph. The Bi-Cayley graph BC(G, S) is connected if and only if S^-1S generates G. In this thesis, we consider connected cubic Bi-Cayley graphs and a special Bi-Cayley graph for the symmetric group. Let S_n = Sym(n) be the symmetric group on the set {1, 2,…, n}, T_n is a set of identity element and all transpositions of Sym(n). Since T_n^-1T_n is a generating set of S_n, then the Bi-Cayley graph BC(S_n,T_n) is connected. A graph X is said to be super-connected if every minimum vertex cut isolates a vertex. Similarly, a graph X is said to be hyper-connected if every minimum vertex cut creats two components, one of which is an isolated vertex. In [8], D.Wang and J.Meng characterized super-connected and hyper-connected cubic transitive graphs. Inspired from the paper, we intend to characterize super-connected and hyper-connected cubic Bi-Cayley graphs and BC(S_n,T_n). The followings are our main results:1. connected cubic Bi-Cayley graphs are super-connected2. connected cubic Bi-Cayley graphs are hyper-connected if and only if BC(G, S)(?) K_3,3.3. BC(S_n,T_n) is hyper-connected.