The Super Restricted Edge Connectivity of Kautz Undirected Graphs
Shiying Wang and Shangwei Lin
School of Mathematical Sciences, Shanxi University,
Taiyuan 030006,
P.R. China
Abstract
The restricted edge connectivity is a more
refined network reliability index than edge connectivity. The
restricted edge connectivity ¦Ë'(G) of graph G is the
minimum number of edges whose removal disconnects G into
non-trivial components. Moreover, G is super restricted edge
connected if its every minimum restricted edge cut separates exactly
one edge. In this paper, we study a kind of the important model of
networks-Kautz undirected graphs UK(d,n), and show the following:
for d¡Ý3, n¡Ý2,
¦Ë'(UK(d,n))=4d-4 and UK(d,n) is a super restricted edge connected graph.
