Connectivity and Super-Connectivity of Bi-Cayley Graphs

Xiaodong Liang
College of Mathematics and System Sciences, Xinjiang University, Xinjiang 830046, P. R. China

Abstract     Full Text  PPT

Let $G$ is a finite group and $S$ is a subset (possibly, contains the identity element) of $G$, we define the Bi-Cayley graph $X{=}BC(G,S$) to be the bipartite graph with vertices $G{\times}\{ 0,1\}$ and edges$\{\{(g,0),(sg,1)\}:g{\in}G,s{\in}S\}$. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex.

At first, we show that if $X{=}BC(G,S$) is connected, then $\kappa(X){=}\delta(X)$. In the next, we characterized the vertex transitive Bi-Cayley graphs which are superconnected or hyper-connected. In addition, we proved that any bipartite Cayley graph is isomorphic to a Bi-Cayley graph.