Hostname: page-component-7b7567c8c-8p88z Total loading time: 0 Render date: 2026-11-19T20:30:09.499Z Has data issue: false hasContentIssue false

Vertex-transitive graphs which are not Cayley graphs, I

Published online by Cambridge University Press:  09 April 2009

Brendan D. McKay
Affiliation:
Computer Science Department, Australian National University, ACT 0200, Australia, bdm@cs.anu.edu.au
Cheryl E. Praeger
Affiliation:
Department of Mathematics, University of Western Australia, Nedlands, WA 6009, Australia, praeger@maths.uwa.edu.au
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph which is not a Cayley graph. We consider the problem of determining the orders of such graphs. In this, the first of a series of papers, we present a sequence of constructions which solve the problem for many orders. In particular, such graphs exist for all orders divisible by a fourth power, and all even orders which are divisible by a square.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1994