The problem of defining cycles in infinite graphs has received much attention in the literature. Diestel and Kuhn have proposed viewing a graph as 1-complex, and defining a topology on the point set of the graph together with its ends. In this setting, a circle in the graph is a homeomorph of the unit circle S^1 in this topological space. For locally finite graphs this setting appears to be natural, as many classical theorems on cycles in finite graphs extend to the infinite setting.
A Hamilton circle in a graph is a circle containing all the vertices of the graph.
We exhibit a necessary and sufficient condition that a countable graph contain a Hamilton circle in terms of the existence of Hamilton cycles in an increasing sequence of finite graphs.
As corollaries, we obtain extensions to locally finite graphs of Zhan's theorem that all 7-connected line graphs are hamiltonian (confirming a conjecture of Georgakopoulos), and Ryjacek's theorem that all 7-connected claw-free graphs are hamiltonian. A third corollary of our main result is Georgakopoulos' theorem that the square of every two-connected locally finite graph contains a Hamilton circle (an extension of Fleischner's theorem that the square of every two-connected finite graph is Hamiltonian).
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1369 |
| Date | 28 April 2009 |
| Creators | Funk, Daryl J. |
| Contributors | Brewster, Richard |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.003 seconds