기초과학연구원 이산수학그룹
On December 3, 2020, Deniz Sarikaya from Universität Hamburg gave an online talk about necessary conditions for locally finite graphs to have a Hamiltonian cycle in terms of their forbidden induced subgraphs. The title of his talk was “What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs“.
The study of Hamiltonian graphs, i.e. finite graphs having a cycle that contains all vertices of the graph, is a central theme of finite graph theory. For infinite graphs such a definition cannot work, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2,3], which allows to generalize several results about being a Hamiltonian graph to locally finite graphs, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$ in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1].
We examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs, claw- and bull-free graphs, the last also about further graph classes being structurally richer, where we focus on paws as relevant subgraphs, but relax the condition of forbidding them as induced subgraphs.
The goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details.
This is based on joint work [4,5] with Karl Heuer.
[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics, vol 173. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8
[2] R. Diestel and D. Kühn, On infinite cycles I, Combinatorica 24 (2004), pp. 69-89.
[3] R. Diestel and D. Kühn, On infinite cycles II, Combinatorica 24 (2004), pp. 91-116.
[4] K. Heuer and D. Sarikaya, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls, arXiv:2006.09160
[5] K. Heuer and D. Sarikaya, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws, arXiv:2006.09166