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⊆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)<29 (k+1)2 for some S⊆V(G) with 13 (k+1)⩽|S|⩽12 n, then G has a factor F such that G/E(F) is vertex-transitive and each component of F is an isomorphic vertex-transitive graph on at least 23 (k+1) vertices. We show that this result is in some sense best possible and use it to show that if k⩾4 and G has an edge cut of size less than 15 (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.