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’\) 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’\)-optimal if \(\lambda'(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 \geq 2\) and \(n\geq 1\) the Kautz undirected graph \(UK(d, 1)\) is \(\lambda’\)-optimal except \(UK(2,1)\) and \(UK(2,2)\) and, hence, is super edge-connected except \(UK(2, 2)\).