On 3-restricted edge connectivity of undirected binary Kautz graphs

An edge cut of a connected graph is mm-restricted if its removal leaves every component having order at least mm. The size of minimum mm-restricted edge cuts of a graph GG is called its mm-restricted edge connectivity. It is known that when m≤4m≤4, networks with maximal mm-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n)UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge.