Super-connectivity and super-edge-connectivity for some interconnection networks

Abstract

Let G = (V, E) be a k-regular graph with connectivity K and edge connectivity. G is maximum connected if kappa = k, and G is maximum edge connected if lambda = k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x(v,x) is an element of E} for some vertex v is an element of V; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)(v,x) is an element of E} for some vertex v is an element of V. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, mobius cubes, split-stars, and recursive circulant graphs. (C) 2002 Elsevier Science Inc. All rights reserved.