Hamilton Decompositions of Graphs with Primitive Complements

Abstract

A graph G is a pair (V, E) where V is the set of vertices(or nodes) and E is the set of edges connecting the vertices. A graph is called k-regular, if all of its vertices are incident with k edges. A k-factor of a graph G is a k-regular spanning subgraph of G, and a Hamilton cycle is a connected 2-factor. So, a Hamilton cycle in G is a cycle that passes through all the vertices of G. A regular graph is called primitive, if it has no proper factors.

Also, a Hamilton decomposition of a graph G is a partition of the edges of G into edge-disjoint Hamilton cycles. Decompositions of graphs into Hamilton cycles with no Hamilton cycles in the complement, and into 2-factors with no 2-factors in the complement have been done in previous studies by D.G. Hoffman, C.A. Rodger, and A. Rosa. In this study, we find necessary and sufficient conditions for the existence of Hamilton decompositions of graphs with primitive complements. We also find sufficient conditions for the existence of Hamilton decompositions of graphs where the primitive complement is in a complete multipartite graph. We use a graph homomorphism technique, called amalgamation, for the proofs of the main results.