This is joint work by Peter Adams (The University of Queensland, Australia), Hayri Ardal (Simon Fraser University, Canada), J\'{a}n Ma\v{n}uch (Simon Fraser University, Canada), Moshe Rosenfeld (University of Washington, USA) and Ladislav Stacho (Simon Fraser University, Canada).

As part of this work, we have searched for spanning cubic graph designs of order 16.

The following file contains information on the existence (or otherwise) of spanning cubic graph designs of order 16.

• Text file of spanning cubic graph decompositions of order 16.

The 4207 (connected and disconnected) cubic graphs of order 16 were generated using Brendan McKay's nauty program. These graphs are presented in the file in the same order in which they were generated by nauty. The entry for each graph is in the form:

• On the first line, the letter "G", followed by the graph number (from 1 to 4207), followed by the text "E:", followed by the 24 edges in the edge-set of the graph as generated by nauty. Each edge is presented as a pair of vertices, in the range 0 to 15.
• On the second line, the letter "G", followed by the graph number, followed by the text "C:" (if a cyclic decomposition exists), or the text "N:" (if a cyclic decomposition does not exist but a non-cyclic decomposition does exist), or the text "F:" (if no decomposition exists).

  If a cyclic decomposition exists, then the vertex set of K_{16} is {i_j}\cup {INF}, i=0,1,2,3,4 and j=0,1,2. Each decomposition is presented as a 16-tuple, and the complete decomposition obtained by cycling the given 16-tuple modulo 5, keeping the subscript and the vertex INF fixed.

  If a non-cyclic decomposition exists then it is presented as five 16-tuples, one per line.

• Nine graphs admit non-cyclic decompositions of K_{16} (Graphs 1, 2, 1187, 3622, 3630, 3739, 4167, 4205 and 4206).
• Three graphs do not admit decompositions of K_{16} (Graphs 1978, 3629 and 4198).

Back to Peter's Homepage