Generalisations of the Doyen-Wilson Theorem
thesis
posted on 2017-03-29, 00:17 authored by Rosalind A. HoyteIn 1973, Doyen and
Wilson famously solved the problem of when a 3-cycle system can be embedded in
another 3-cycle system. There has been much interest in the literature in
generalising this result for m-cycle systems when m > 3. Although
there are several partial results, including complete solutions for some small
values of m and strong partial results for even m, this still remains an open
problem.
The main results of this thesis concern generalisations of the Doyen-Wilson Theorem for odd m-cycle systems and cycle decompositions of the complete graph with a hole. The complete graph of order v with a hole of size u, Kv - Ku, is constructed from the complete graph of order v by removing the edges of a complete subgraph of order u (where v ≥ u).
For each odd m ≥ 3 we completely solve the problem of when an m-cycle system of order u can be embedded in an m-cycle system of order v, barring a finite number of possible exceptions. The problem is completely resolved in cases where u is large compared to m, where m is a prime power, or where m ≤ 15. In other cases, the only possible exceptions occur when v - u is small compared to m. This result is proved as a consequence of a more general result which gives necessary and sufficient conditions for the existence of an m-cycle decomposition of Kv - Ku in the case where u ≥ m - 2 and v - u ≥ m + 1 both hold.
We prove that Kv - Ku can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, v - u ≥ 10, each cycle has length at most min(u,v - u), and the longest cycle is at most three times as long as the second longest. This complements existing results for cycle decompositions of graphs such as the complete graph, complete bipartite graph and complete multigraph.
We obtain these cycle decomposition results by applying a cycle switching technique to modify cycle packings of Kv - Ku. The tools developed by cycle switching enable us to merge collections of short cycles to obtain longer cycles. The methodology therefore relies on first finding decompositions of various graphs into short cycles, then applying the merging results to obtain the required decomposition. Similar techniques have previously been successfully applied to the complete graph and the complete bipartite graph. These methods also have potential to be further developed for the complete graph with a hole as well as other graphs.
We also give a complete solution to the problem of when there exists a packing of the complete multigraph with cycles of arbitrary specified lengths. The proof of this result relies on applying cycle switching to modify cycle decompositions of the complete multigraph obtained from known results.
The results in this thesis make substantial progress toward generalising the Doyen-Wilson Theorem for arbitrary odd cycle systems and toward constructing cycle decompositions of the complete graph with a hole. However there still remain unsolved cases. Moreover, the cycle switching and base decomposition methods used to obtain these results give rise to several interesting open problems.
The main results of this thesis concern generalisations of the Doyen-Wilson Theorem for odd m-cycle systems and cycle decompositions of the complete graph with a hole. The complete graph of order v with a hole of size u, Kv - Ku, is constructed from the complete graph of order v by removing the edges of a complete subgraph of order u (where v ≥ u).
For each odd m ≥ 3 we completely solve the problem of when an m-cycle system of order u can be embedded in an m-cycle system of order v, barring a finite number of possible exceptions. The problem is completely resolved in cases where u is large compared to m, where m is a prime power, or where m ≤ 15. In other cases, the only possible exceptions occur when v - u is small compared to m. This result is proved as a consequence of a more general result which gives necessary and sufficient conditions for the existence of an m-cycle decomposition of Kv - Ku in the case where u ≥ m - 2 and v - u ≥ m + 1 both hold.
We prove that Kv - Ku can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, v - u ≥ 10, each cycle has length at most min(u,v - u), and the longest cycle is at most three times as long as the second longest. This complements existing results for cycle decompositions of graphs such as the complete graph, complete bipartite graph and complete multigraph.
We obtain these cycle decomposition results by applying a cycle switching technique to modify cycle packings of Kv - Ku. The tools developed by cycle switching enable us to merge collections of short cycles to obtain longer cycles. The methodology therefore relies on first finding decompositions of various graphs into short cycles, then applying the merging results to obtain the required decomposition. Similar techniques have previously been successfully applied to the complete graph and the complete bipartite graph. These methods also have potential to be further developed for the complete graph with a hole as well as other graphs.
We also give a complete solution to the problem of when there exists a packing of the complete multigraph with cycles of arbitrary specified lengths. The proof of this result relies on applying cycle switching to modify cycle decompositions of the complete multigraph obtained from known results.
The results in this thesis make substantial progress toward generalising the Doyen-Wilson Theorem for arbitrary odd cycle systems and toward constructing cycle decompositions of the complete graph with a hole. However there still remain unsolved cases. Moreover, the cycle switching and base decomposition methods used to obtain these results give rise to several interesting open problems.
