On the edge connectivity, hamiltonicity, and toughness of vertex-transitive graphs

Let G be a connected k-regular vertex-transitive graph on n vertices. For S subset of or equal to V(G) let d(S) denote the number of edges between S and V(G)\ S. We extend results of Mader and Tindell by showing that if d(S) < 2/9(k + 1)(2) for some S subset of or equal to V(G) with 1/3(k + 1) less than or equal to \ S \ less than or equal to 1/2n, then G has a factor F such that Gift Fl is vertex-transitive and each component of F is an isomorphic vertex-transitive graph on at least 2/3 (k + 1) vertices. We show that this result is in some sense best possible and use it to show that if k greater than or equal to 4 and G has an edge cut of size less than 1/5 (8k - 12) which separates G into two components each containing at least two vertices. then G is hamiltonian. We also obtain as a corollary a result on the toughness of vertex-transitive graphs. (C) 1999 Academic Press.