Computationally constructed two-factorisations of graphs of orders fifteen and seventeen |
There are 17 non-isomorphic 2-regular graphs of order 15, and 25 non-isomorphic 2-regular graphs of order 17. Consequently, there are 245,157 possible types of 2-factorisations of K_{15}, and 10,518,300 possible types of 2-factorisations of K_{17}. In [1] we show that all except five possible types of 2-factorisations exist for K_{15}, and that all possible types of 2-factorisations exist for K_{17}. The results in [1] rely on a large number of computationally constructed 2-factorisations of various graphs, which are presented in this research report. The existence or otherwise of all possible types of 2-factorisations of K_n is now settled for all n<=17.
[1] Peter Adams and Darryn Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen (submitted).
If G is a graph with n vertices, then the vertices of G are labelled {0,1,..., n-1}. A 2-regular connected graph on m vertices is written as (v1,v2,...,vm). For brevity, commas are omitted between cycles in each 2-factor. In [1], the type of a 2-factor is written in the form [A1,...,Ad]. Here, square brackets and commas are omitted. Finally, the type of each 2-factor is identified by a one or two character label, which is used to give a short-hand notation for the type of each 2-factorisation. The top of each file shows the correspondence between these labels and the 2-factors.
The following 2-factorisations are available on this site, all as text documents: