Restricted Edge Connectivity of Binary Undirected Kautz Graphs
Jianping Ou · Shuxue jikan · 2004
A restricted edge cut is an edge cut of a connected graph whose removal results in a disconnected graph without isolated vertices. The size of a minimum restricted edge cut of a graph G is called its restricted edge connectivity, and is denoted by λ(G). Letξ(G) be the minimum edge degree of graph G. It is known that λ(G)≤ξ(G) if G contains restricted edge cuts. Graph G is called maximal restricted edge connected if the equality holds in the the preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to be maximal restricted edge connected if n ≥ 2.