Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples

Michael Haythorpe, Andrew Johnson

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
3 Downloads (Pure)

Abstract

A very old problem in campanology is the search for peals. The latter can be thought of as a heavily constrained sequence of all possible permutations of a given size, where the exact nature of the constraints depends on which method of ringing is desired. In particular, we consider the methods of bobs-only Stedman Triples and Erin Triples; the existence of the latter is still an open problem. We show that this problem can be viewed as a similarly constrained (but not previously considered) form of the Hamiltonian cycle problem (HCP). Through the use of special subgraphs, we convert this to a standard instance of HCP. The original problem can be partitioned into smaller instances, and so we use this technique to produce smaller instances of HCP as well. We note that the instances known to have solutions provide exceptionally difficult instances of HCP.

Original languageEnglish
Pages (from-to)61-75
Number of pages15
JournalElectronic Journal of Graph Theory and Applications
Volume7
Issue number1
DOIs
Publication statusPublished - 2019

Bibliographical note

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Keywords

  • change ringing
  • triples
  • Stedman
  • Erin
  • Hamiltonian cycles
  • campanology
  • Triples
  • Change ringing

Fingerprint Dive into the research topics of 'Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples'. Together they form a unique fingerprint.

Cite this