Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9619September 1996 
Jan van den Heuvel and Bill Jackson
Abstract
Let $G$ be a connected $k$regular vertextransitive graph on $n$ vertices. We extend results of Mader, Watkins, and Tindell by showing that if $d(S) < \frac{2}{9}(k+1)^2$ for some $S \subseteq V(G)$ with $\frac{2}{3}(k+1) < S \leq \frac{1}{2}n$, then $G$ has a factor $F$ such $G/E(F)$ is vertextransitive and each component of $F$ is an isomorphic vertextransitive graph on at least $\frac{2}{3}(k+1)$ vertices. We deduce that $G$ is hamiltonian for the special case when $k \geq 4$ and $d(S) < \frac{1}{5}(8\,k12)$. We also obtain as a corollary a result on the toughness of vertextransitive graphs.
Keywords: vertextransitive graph, edge connectivity, hamiltonicity, toughness
AMS Subject Classifications (1991): 05C25, 05C40, 05C45
If you would like a free copy of this report, please send the number of this report, LSECDAM9619, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)171955 7732. Fax: +44(0)171955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html