Twin Bob Plan Composition of Stedman Triples: Partitioning of Graphs into Hamiltonian Subgraphs
Research Report 94-37
Date: 7 Nov 1994
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
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.
campanology. Stedman Triples. Hamiltonian directed graphs.
AMS Subject Classification (1991)
Secondary: 05C20, 05C25, 05C45
The paper is available in the following forms:
- 2bob-sted.ps.gz (51kB) or
To minimize network load, please choose the smaller gzipped .gz form if
and only if your browser client supports it.
Sydney Mathematics and Statistics