A subset $F$ of edges in a connected graph $G$ is a $h$-extra edge-cut if $G-F$ is disconnected and every component has more than $h$ vertices. The $h$-extra edge-connectivity $\la^{ (h)}(G)$ of $G$ is defined as the minimum cardinality over all $h$-extra edge-cuts of $G$. A graph $G$, if $\la^{ (h)}(G)$ exists, is super-$\la^{ (h)}$ if every minimum $h$-extra edge-cut of $G$ isolates at least one connected subgraph of order $h+1$. The persistence $\rho^{ (h)}(G)$ of a super-$\la^{ (h)}$ graph $G$ is the maximum integer $m$ for which $G-F$ is still super-$\la^{ (h)}$ for any set $F\subseteq E(G)$ with $|F|\leqslant m$. Hong { \it et al.} [Discrete Appl. Math. 160 (2012), 579-587] showed that $\min\{ \la^{ (1)}(G)-\delta(G)-1,\delta(G)-1\}\leqslant \rho^{ (0)}(G)\leqslant \delta(G)-1$, where $\delta(G)$ is the minimum vertex-degree of $G$. This paper shows that $\min\{ \la^{ (2)}(G)-\xi(G)-1,\delta(G)-1\}\leqslant \rho^{ (1)}(G)\leqslant \delta(G)-1$, where $\xi(G)$ is the minimum edge-degree of $G$. In particular, for a $k$-regular super-$\la'$ graph $G$, $\rho^{ (1)}(G)=k-1$ if $\la^{ (2)}(G)$ does not exist or $G$ is super-$\la^{ (2)}$ and triangle-free, from which the exact values of $\rho^{ (1)}(G)$ are determined for some well-known networks.

Categories: math.CO

Vulnerability of super edge-connected graphs