The super-connected property of recursive circulant graphs

Abstract

In a graph G, a k-container C-k(u, v) is a set of k disjoint paths joining u and v. A k-container C-k(u, V) is K*-container if every vertex of G is passed by some path in C-k(u, v). A graph G is k*-connected if there exists a k*-container between any two vertices. An m-regular graph G is super-connected if G is k*-connected for any k with 1 less than or equal to k less than or equal to m. In this paper, we prove that the recursive circulant graphs G(2(m), 4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m not equal 2. (C) 2004 Elsevier B.V. All rights reserved.