Some results on Steiner Triple Systems and Cycle Decompositions

Daniel Horsley (2008). Some results on Steiner Triple Systems and Cycle Decompositions PhD Thesis, School of Physical Sciences, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
n33585617_phd_abstract.pdf n33585617_phd_abstract.pdf application/pdf 137.39KB 0
n33585617_phd_content.pdf n33585617_phd_content.pdf application/pdf 8.22MB 0
n33585617_phd_front.pdf n33585617_phd_front.pdf application/pdf 332.54KB 0
n33585617_phd_totalthesis.pdf n33585617_phd_totalthesis.pdf application/pdf 8.54MB 0
Author Daniel Horsley
Thesis Title Some results on Steiner Triple Systems and Cycle Decompositions
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2008-01-01
Thesis type PhD Thesis
Supervisor Bryant, Darryn E.
Maenhaut, Barbara
Subjects 240000 Physical Sciences
Formatted abstract
This thesis is comprised of four chapters, each of which contains results related to Steiner
triple systems or to cycle decompositions of graphs. Each chapter contains its own introduction
which gives a background to the problems considered as well as introducing any results,
concepts and notation which will be required. The work presented in the first and second
chapters has been published in [15] and [11]. The work presented in the third and fourth
chapters has been submitted for publication [13, 14].
The first chapter deals with partial cycle systems and decompositions of complete graphs
into 2-regular graphs. It is shown that the existence of a partial cycle system implies the
existence of an equitable partial cycle system with cycles of the same lengths. This result is
then used to show that the obvious necessary conditions for decomposing a complete graph
into 2-regular subgraphs of specified sizes are also sufficient. The result on equitable partial
cycle systems generalises work done by Andersen et al [Q], and Raines and Szaniszl6~
result on decompositions of complete graphs into 2-regular graphs uses and complements a
result of Balister [7].
In the second chapter necessary and sufficient conditions are given for the existence of
a partial Steiner triple system with two disjoint holes of specified sizes, that is, a 3-cycle
decomposition of the graph obtained from the complete graph by removing the edges of two
vertex-disjoint complete subgraphs. This generalises the well-known Doyen- Wilson Theorem
[25]. The decompositions obtained yield new group divisible designs with block size 3.
The third chapter is a proof of Lindner's conjecture [34] that any partial Steiner triple
system of order u has an embedding in a Steiner triple system of order v if v = 1,3 (mod 6)
and v > 2u+ 1. The lower bound on v given by Lindner's conjecture is sharp in the sense that
for all u > 9 there exists a partial Steiner triple system of order u which cannot be embedded
in a Steiner triple system of order v for any v < 2u + 1 ~. This result subsumes various
partial results which had been obtained on Lindner's conjecture by Treash [44], Lindner [33],
Andersen et al [5], and Bryant [9].
In the fourth chapter a new technique for packing edge disjoint cycles of arbitrary specified
lengths in complete graphs is introduced. The technique is used to prove new results on
packings of the complete graph with cycles of arbitrary specified lengths, maximum packings
of the complete graph with uniform length cycles, and cycle decompositions of the complete
graph. Solutions to many cases of Alspach's cycle decomposition problem ~ are obtained,
and the result on packings produces "near solutions" to the problem.


 
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 19 Sep 2008, 01:35:36 EST by Noela Stallard on behalf of Library - Information Access Service