Electronic Theses and Dissertations

# Hamilton Decompositions of Graphs with Primitive Complements

﻿
dc.contributor.authorOzkan, Sibelen_US
dc.date.accessioned2008-09-09T21:23:36Z
dc.date.available2008-09-09T21:23:36Z
dc.date.issued2007-05-15en_US
dc.identifier.urihttp://hdl.handle.net/10415/813
dc.description.abstractA 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.en_US
dc.language.isoen_USen_US
dc.subjectMathematics and Statisticsen_US
dc.titleHamilton Decompositions of Graphs with Primitive Complementsen_US
dc.typeDissertationen_US
dc.embargo.lengthNO_RESTRICTIONen_US
dc.embargo.statusNOT_EMBARGOEDen_US