Twin Bob Plan Composition of Stedman Triples: Partitioning of Graphs into Hamiltonian Subgraphs

Author

Deryn Griffiths

Status

Research Report 94-37
Date: 7 Nov 1994

Abstract

This paper considers finite directed graphs with in-degree 2 and out-degree 2 and uses the fact that every edge

belongs to a unique alternating 2n-gon

for some n.

A covering of a directed graph is a collection of disjoint directed circuits which together use each vertex of the graph exactly once. Thus a covering partitions the vertices of a graph, each associated subgraph being Hamiltonian.

The paper shows how to transform one covering into a new one. Each step of the transformation involves all the edges of an alternating 2n-gon. It is shown how the parity of the number of circuits in the covering at each step changes or not according to the parity of n.

This result is applied to bell-ringing and it is shown that there is no Twin-Bob extent of Stedman Triples.

Key phrases

campanology. Stedman Triples. Hamiltonian directed graphs.

AMS Subject Classification (1991)

Primary: 05C90
Secondary: 05C20, 05C25, 05C45

Content

The paper is available in the following forms:

PostScript:: 2bob-sted.ps.gz (51kB) or 2bob-sted.ps (208kB)

To minimize network load, please choose the smaller gzipped .gz form if and only if your browser client supports it.

Sydney Mathematics and Statistics