Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-96-19 September 1996

Abstract

Let $G$ be a connected $k$-regular vertex-transitive 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 vertex-transitive and each component of $F$ is an isomorphic vertex-transitive 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\,k-12)$. We also obtain as a corollary a result on the toughness of vertex-transitive graphs.

Keywords: vertex-transitive 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, LSE-CDAM-96-19, 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)-171-955 7732. Fax: +44(0)-171-955 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