Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-96-19

September 1996

On the Edge Connectivity, Hamiltonicity and Toughness of Vertex-Transitive Graphs

Jan van den Heuvel and Bill Jackson


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.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html