The Restricted Edge-Connectivity of Kautz 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 connected component has at least two vertices. A graph $G$ is called ${\lambda }^{\prime }$-optimal if ${\lambda }^{\prime }(G)=min\{d_G(u)+d_G(v)-2:uv\text{ is an edge in }G\}$. This paper proves that for any $d$ and $n$ with $d\ge 2$ and $n\ge 1$ the Kautz undirected graph $UK(d,1)$ is ${\lambda }^{\prime }$-optimal except $UK(2,1)$ and $UK(2,2)$ and, hence, is super edge-connected except $UK(2,2)$.