Localization theorems in Hamiltonian graph theory
Armen Asratian (Linköping University)
A Hamilton cycle of a graph G is a walk in G that starts and finishes at the same vertex and visits each other vertex exactly once. A Hamilton path of a graph G is a path that includes each vertex of G exactly once. Some problems in algebra and combinatorics can be formulated as problems of the existence of a Hamilton path or cycle in an appropriate graph.
It is known that the classical global criteria for the existence of Hamilton cycles and paths only apply to the graphs with large edge density and small diameter.
In 1984-1990 A. Asratian and N. Khachatryan developed some local criteria for the existence of Hamilton cycles in a connected graph, which are analogues of the global criteria due to Dirac, Ore and others. The idea was to show that the global concept of hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. This local approach gives the possibility to find new classes of graphs with Hamilton cycles which, in particular, also contain infinite subclasses of graphs with small edge density and large diameter.
I will give a review of this topic and present some new results.