Consistent cycles in graphs and digraphs

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

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Let Γ be a finite digraph and let G be a subgroup of the automorphism group of Γ. A directed cycle [InlineMediaObject not available: see fulltext.] of Γ is called G-consistent whenever there is an element of G whose restriction to [InlineMediaObject not available: see fulltext.] is the 1-step rotation of [InlineMediaObject not available: see fulltext.]. Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in his public lectures at the Second British Combinatorial Conference in 1971. He observed that the number of G-orbits of G-consistent cycles of an arc-transitive group G is precisely one less than the valency of the graph. In this paper, we give a detailed proof of this result in a more general setting of arbitrary groups of automorphisms of graphs and digraphs.

Original languageEnglish (US)
Pages (from-to)205-216
Number of pages12
JournalGraphs and Combinatorics
Volume23
Issue number2
DOIs
StatePublished - Apr 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Consistent cycles in graphs and digraphs'. Together they form a unique fingerprint.

Cite this