Loading Events

« All Events

  • This event has passed.
:

Deniz Sarikaya, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs

Thursday, December 3, 2020 @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

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.

Bibliography

[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 bullsarXiv:2006.09160

[5] K. Heuer and D. Sarikaya, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: pawsarXiv:2006.09166

Details

Date:
Thursday, December 3, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.