On a kind of restricted edge connectivity of graphs (Q1348390)

Let \(G=(V,E)\) be a connected graph. A subset \(S\) of \(E\) is called an edge cut, if \(G-S\) is disconnected. If all components of \(G-S\) contain at least \(m\) vertices, it is called an \(m\)-restricted edge cut. The minimum size of an \(m\)-restricted edge cut is called the \(m\)-restricted edge connectivity \(\lambda^{(m)}\). For a subset \(X\) of \(V\), the number of edges between \(X\) and \(V\setminus X\) is denoted by \(\omega(X)\). The quantity \(\xi_m\) is defined to be \(\min\{\omega(X): X\subseteq V\), \(|X|=m\) and \(G[X]\) is connected\}. Note that \(\xi_1\) equals the minimum degree of a vertex and \(\xi_2\) is the minimum edge degree. If \(G\) has at least \(4\) vertices and is not a star, \(\lambda^{(2)}\) is finite and satisfies \(\lambda^{(1)}\leq \lambda^{(2)}\leq \xi_2\); see \textit{F. T. Boesch} and \textit{J. F. Wang} [SIAM J. Algebraic Discrete Math. 7, 89-98 (1986; Zbl 0578.05046)]. If \(\lambda^{(3)}\) is finite, the relation \(\lambda^{(2)}\leq \lambda^{(3)}\leq \xi_3\) holds. The authors define a connected graph to be {super-\(\lambda^{(3)}\)}, if \(\lambda^{(m)}=\xi_m\) for \(1\leq m\leq 3\). This is a specialization of the notions {super-\(\lambda\)} (which implies \(\lambda^{(1)}=\xi_1\)) defined by \textit{D. Bauer} et al. [The theory and application of graphs, 45-54 (1981; Zbl 0469.05044)] and optimal super-\(\lambda\) (super-\(\lambda\) with \(\lambda^{(2)}=\xi_2\)), defined by \textit{Q. Li} and \textit{Q. Li} [Networks 31, 61-65 (1998; Zbl 0929.05052)]. The main results of the present paper are the following: If \(G\) is regular with at least \(6\) vertices, then \(\lambda^{(3)}\) is finite. If \(G\) is edge transitive and vertex transitive, i.e., the automorphism group acts transitively on the edges and on the vertices, and is not a cycle, it is super-\(\lambda^{(3)}\). Thus star graphs and hypercubes are super-\(\lambda^{(3)}\). Furthermore, an explicit formula for the number of \(i\)-element edge cuts for \(k\)-regular super-\(\lambda^{(3)}\) graphs and \(2k-2\leq i\leq \xi_3-1\) is given. Finally, a characterization of the super-\(\lambda^{(3)}\) property for circulant graphs \(C_n(a_1,\dots,a_k)\), i.e., the graphs with vertices \(1,\dots, n\) where \(i\) and \(j\) are adjacent if and only if \(i-j\equiv \pm a_s \pmod n\) for some \(s\), is given. As a consequence, the Harary graphs \(C_n(1,2,\dots,k)\) with \(2\leq k<n/2\) are super-\(\lambda^{(3)}\).