The restricted edge-connectivity of Kautz undirected graphs
Yingmei Fan, Jun‐Ming Xu, Min Lü · 2006
A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity λ ′ 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 λ ′-optimal if λ ′ (G) = min{dG(u) + dG(v) − 2: uv is an edge in G}. This paper proves that for any d and n with d ≥ 2 and n ≥ 1 the Kautz undirected graph UK(d, n) is λ ′-optimal except UK(2, 1) and UK(2, 2) and, hence, is super edge-connected except UK(2, 2). Keywords: Edge-connectivity, Restricted edge-connectivity, Super edge-connected, Kautz graphs