Basic Research Project J1-9108
Traversability of vertex-transitive graphs
Project Title: Traversability of vertex-transitive graphs
PI: Klavdija Kutnar
Project Code: J1-9110
Type of the Project: basic research project.
Funding Organization: Slovenian Research Agency (ARRS).
Research Field (ARRS): 1.01.00 - Natural Sciences and Mathematics / Mathematics.
Duration: 1. 7. 2018 - 30. 6. 2021.
Project Category: B.
Yearly Range: 0.86 FTE (1.468 research hours).
Sicris profile of the project is avaliable here.
Research Organizations:
University of Primorska, Andrej Marušič Institute,
University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies,
University of Ljubljana, Faculty of Education,
InnoRenew CoE.
Project Members:
| Kutnar Klavdija (leader, ARRS code: 24997) |
| Hujdurović Ademir (ARRS code: 32518) Miklavič Štefko (ARRS code: 21656) |
| Požar Rok (ARRS code: 32026) |
| Milanič Martin (ARRS code: 30211) |
| Frelih Boštjan (ARRS code: 24999) Šparl Primož (ARRS code: 23341) |
| Kiss Gyorgy (ARRS code: 38347) |
| Szonyi Tamas (ARRS code: 51192) |
| Burnard Michael (ARRS code: 36182) |
| Kresz Miklos (ARRS code: 50985) |
| Filipovski Slobodan (ARRS code: 37715) |
| Nevena Mitrović (ARRS code: 50673) |
| Penjić Safet (ARRS code: 37553) |
| Žiga Velkavrh (ARRS code 50720) |
Abstract:
The project considers the prominent outstanding unsolved problem posed by Lovász in 1969 which ties together two seemingly unrelated concepts – traversability and symmetry: Does every finite connected vertex-transitive graph (a graph X with its automorphism group Aut(X) acting transitively on the vertex set V(X), or a VTG for short) have a Hamilton path (a simple path visiting all vertices of the graph)?
No connected VTG without a Hamilton path is known to exist; moreover, only four connected VTGs on at least three vertices not having a Hamilton cycle – a simple cycle containing all vertices of the graph – are known so far. None of these four exceptional graphs is a Cayley graph, that is, a VTG with a regular subgroup of automorphisms (a Cayley group). This has led to a folklore conjecture that every connected Cayley graph possesses a Hamilton cycle.
In the project the problem of the existence of Hamilton paths and cycles in connected VTGs will be referred to as the HPC problem. This problem has served as one of the main catalysts in the recent development of algebraic graph theory, one of the fastest growing research areas in discrete mathematics. Cubic VTGs hold a central position in the ongoing research for an obvious reason: scarcity of edges intuitively makes it harder to find paths or cycles, which is supported by the fact that all known VTGs without Hamilton cycles are cubic.
The project aim is to make significant contribution to the HPC problem with special emphasis given to existence of Hamilton cycles in Cayley graphs.