Designs on Cubic Multigraphs

Abstract

<p>Necessary conditions are found for the existence of graph designs on cubic multigraphs. It is shown that, with a few given exceptions, these conditions are sufficient for all connected cubic multigraphs on six or fewer vertices, and for four of the five disconnected ones. Partial results are obtained for the remaining multigraph, which consists of a K4 and a 3K2 component. Necessary and sufficient conditions for the existence of resolvable designs on all bipartite cubic multigraphs on six or fewer vertices are found. Graceful labellings are given for all cubic graphs on eight or ten vertices, and for all prisms on eighteen or fewer vertices. These are used to find some designs on these graphs, including some infinite classes. In addition, some small designs are found for the 5-prism and the Petersen graph, and some results are given for cubes.</p>