Restricted Edge Connectivity of Edge Transitive Graphs

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,\dots ,{\xi }_3(G)–1$) for edge transitive graph $G$, where $N_i(G)$ denotes the number of edge cuts of size $i$ in $G$.