Arc-transitive cycle decompositions of tetravalent graphs

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

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


A cycle decomposition of a graph Γ is a set C of cycles of Γ such that every edge of Γ belongs to exactly one cycle in C. Such a decomposition is called arc-transitive if the group of automorphisms of Γ that preserve C setwise acts transitively on the arcs of Γ. In this paper, we study arc-transitive cycle decompositions of tetravalent graphs. In particular, we are interested in determining and enumerating arc-transitive cycle decompositions admitted by a given arc-transitive tetravalent graph. Among other results we show that a connected tetravalent arc-transitive graph is either 2-arc-transitive, or is isomorphic to the medial graph of a reflexible map, or admits exactly one cycle structure.

Original languageEnglish (US)
Pages (from-to)1181-1192
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Issue number6
StatePublished - Nov 2008


  • Automorphism group
  • Consistent cycle
  • Cycle decomposition
  • Graph
  • Medial maps

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Arc-transitive cycle decompositions of tetravalent graphs'. Together they form a unique fingerprint.

Cite this