On the number of closed walks in vertex-transitive graphs

The results of Siran and the first author [A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994) 105-114; More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121-132] are generalized, and new formulas for the number of closed walks of length p(r) or pq, where p and q are primes, valid for all vertex-transitive graphs are found. Based on these formulas, several simple tests for vertex-transitivity are presented, as well as lower bounds on the orders of the smallest vertex- and arc-transitive groups of automorphisms for vertex-transitive graphs of given valence. (c) 2006 Elsevier B.V. All rights reserved.