The Restricted Edge-Connectivity of de Bruijn Undirected Graphs

Abstract

A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity ${\lambda }^{\prime }$ of a connected graph is the minimum number of edges whose deletion results in a disconnected graph such that each component has at least two vertices. It has been shown by A. H. Esfahanian and S. L. Hakimi (On computing a conditional edge-connectivity of a graph. Information Processing Letters, 27(1988), 195-199] that ${\lambda }^{\prime }(G)\le \xi (G)$ for any graph of order at least four that is not a star, where $\xi (G)=min\{d_G(u)+d_G(v)–2:uv\text{ is an edge in }G\}$. A graph $G$ is called ${\lambda }^{\prime }$-optimal if ${\lambda }^{\prime }(G)=\xi (G)$. This paper proves that the de Bruijn undirected graph $UB(d,n)$ is ${\lambda }^{\prime }$-optimal except $UB(2,1)$, $UB(3,1)$, and $UB(2,3)$, and hence, is super edge-connected for $n\ge 1$ and $d\ge 2$.