Restricted Edge Connectivity of Edge Transitive Graphs

Zhao Zhang1,2, Jixiang Meng1
1 College of Mathematics and System Sciences, Xinjiang University, Urumdai, Xinjiang, 830046, People’s Republic of China
2Department of Mathematics, Zhengzhou University, Zhengzhou, Henan, 450052, People’s Republic of China

Abstract

Let \(G = (V, E)\) be a connected graph and \(S \subseteq E\). \(S\) is said to be an \(r\)-restricted edge cut if \(G – S\) is disconnected and each component in \(G – S\) contains at least \(r\) vertices. Define \(\lambda^{(r)}(G)\) to be the minimum size of all \(r\)-restricted edge cuts and \(\xi_r(G) = \min\{w(U): U \subseteq V, |U| = r\) and the subgraph of \(G\) induced by \(U\) is connected, where \(w(U)\) denotes the number of edges with one end in \(U\) and the other end in \(V\setminus U\). A graph \(G\) with \(\lambda^{(r)} = \xi_r(G)\) (\(r = 1,2,3\)) is called an \(\lambda^{(3)}\)-optimal graph. In this paper, we show that the only edge-transitive graphs which are not \(\lambda^{(3)}\)-optimal are the star graphs \(K_{1, n-1}\), the cycles \(C_n\), and the cube \(Q_3\). Based on this, we determine the expressions of \(N_i(G)\) (\(i = 0,1,\ldots,\xi_3(G) – 1\)) for edge transitive graph \(G\), where \(N_i(G)\) denotes the number of edge cuts of size \(i\) in \(G\).