Overlap in consistent cycles

Štefko Miklavič, Primož Potočnik, Steve Wilson

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

A (directed) cycle C in a graph Γ is called consistent provided there exists an automorphism of Γ, acting as a 1-step rotation of C. A beautiful but not well-known result of J.H. Conway states that if Γ is arc-transitive and has valence d, then there are precisely d - 1 orbits of consistent cycles under the action of Aut(Γ). In this paper, we extend the definition of consistent cycles to those which admit a k-step rotation, and call them 1/k-consistent. We investigate 1/k-consistent cycles in view of their overlap. This provides a simple proof of the original Conway's theorem, as well as a generalization to orbits of 1/k-consistent cycles. A set of illuminating examples are provided.

Original languageEnglish (US)
Pages (from-to)55-71
Number of pages17
JournalJournal of Graph Theory
Volume55
Issue number1
DOIs
StatePublished - May 2007

Keywords

  • Automorphism group
  • Consistent cycle
  • Graph
  • Symmetry

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Overlap in consistent cycles'. Together they form a unique fingerprint.

Cite this