Extra edge connectivity and isoperimetric edge connectivity (Q941400): Difference between revisions

An edge set \(S\) of a connected graph \(G\) is a \(k\)-extra edge cut, if \(G-S\) is no longer connected, and each component of \(G-S\) has at least \(k\) vertices. The cardinality of a minimum \(k\)-extra edge cut, denoted by \(\Lambda_k(G)\), is the \(k\)-extra edge connectivity of \(G\). The \(k\)-th isoperimetric edge connectivity \(\gamma_k(G)\) is defined as \[ \gamma_k(G) = \min\{\omega(U): U\subset V(G), | U| \geq k, |\overline U| \geq k\}, \] where \(\omega(U)\) is the number of edges with one end in \(U\) and the other end in \(\overline U =V \backslash U\). Write \[ \beta_k(G) = \min\{\omega(U):U \subset V(G),|U|=k\}. \] A graph \(G\) with \(\gamma_j(G) = \beta_j(G)\) (\(j = 1,\dots,k\)) is said to be \(\gamma_k\)-optimal. In this paper, we first prove that \(\Lambda_k(G) = \gamma_k(G)\) if \(G\) is a regular graph with girth \(g \geq k/2\). Then, we show that except for \(K_{3,3}\) and \(K_{4}\), a 3-regular vertex/edge transitive graph is \(\gamma_k\)-optimal if and only if its girth is at least \(k+2\). Finally, we prove that a connected d-regular edge-transitive graph with \(d \geq 6e_{k}(G)/k\) is \(\gamma_k\)-optimal, where \(e_k(G)\) is the maximum number of edges in a subgraph of \(G\) with order \(k\).