A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle. The problem of determining if a graph is Hamiltonian has been studied extensively, and there are many known sufficient conditions for Hamiltonicity. A large portion of these conditions relate the degrees of vertices of the graph to the number of vertices in the entire graph, and thus they can only apply to a limited set of graphs with high edge density. In a series of papers, Asratian and Khachatryan developed local analogues of some of these criteria. These results do not suffer from the same drawbacks as their global counterparts, and apply to wider classes of graphs. In this thesis we study this approach of creating local conditions for Hamiltonicity, and use it to develop local analogues of some classic results. We also study how local criteria can influence other global properties of graphs. Finally, we will see how these local conditions can allow us to extend theorems on Hamiltonicity to infinite graphs.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-156118 |
| Date | January 2019 |
| Creators | Granholm, Jonas |
| Publisher | Linköpings universitet, Matematik och tillämpad matematik, Linköpings universitet, Tekniska fakulteten, Linköping |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Licentiate thesis, comprehensive summary, info:eu-repo/semantics/masterThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Linköping Studies in Science and Technology. Licentiate Thesis, 0280-7971 ; 1840 |
Page generated in 0.002 seconds