Hamilton decompositions of line graphs of perfectly 1-factorisable graphs of even degree.

Abstract

The proof of the following theorem is the main result of this paper: If G is a 2k-regular graph that has a perfect 1-factorisation, then the line graph, L(G), of G is Hamilton decomposable. Consideration is given to Hamilton decompositions of L(K 2k \\Gamma F ). 1 Introduction All graphs considered in this paper are finite and have no loops or multiple edges. By V (G) and E(G) we denote the vertex set and edge set, respectively, of the graph G. By K n we denote the complete graph on n vertices. A cycle is a 2-regular connected graph. A Hamilton cycle in a graph G is a 2-regular connected spanning subgraph of G. A 1-factorisation of a graph G is a partition of E(G) into 1-factors. A perfect 1-factorisation of G is a 1-factorisation of G in which the union of any pair of 1-factors is a Hamilton cycle of G. A graph is said to be perfectly 1-factorisable if it has at least one perfect 1-factorisation. The line graph, denoted by L(G), of a graph G is the graph with vertex set E(G), where...