Prehodnost v točkovno tranzitivnih grafih / Traversability in vertex-transitive graphs
|
Naziv Tittle |
Prehodnost v točkovno tranzitivnih grafih / Traversability in vertex-transitive graphs |
|
Akronim Acronim |
J1-9110 |
|
Opis Description |
(SI) Projekt obravnava dobro poznano odprto domnevo, ki jo je leta 1969 postavil Lovász in povezuje dva navidezno nepovezana pojma - prehodnost in simetrijo: Ali ima vsak povezan točkovno tranzitiven graf (graf X, katerega grupa avtomorfizmov Aut(X) deluje tranzitivno na množici točk V(X) ali TTG na kratko) hamiltonsko pot (enostavno pot, ki vsebuje vse točke grafa)? Protiprimera za zapisano domnevo ne poznamo. Poleg tega so izmed vseh znanih povezanih točkovno tranzitivnih grafov znani le štirje grafi na vsaj treh točkah, ki nimajo hamiltonskega cikla - enostavenega cikla, ki vsebuje vse točke grafa. Dejstvo, da noben izmed teh štirih grafov ni Cayleyev (t.j. TTG, katerega grupa avtomorfizmov premore regularno podgrupo (Cayleyevo grupo)), je pripeljalo do splošne domneve, da ima vsak povezan Cayleyev graf hamiltonski cikel. V projektu bo problem obstoja hamiltonskih poti in ciklov v povezanih TTG-ih poimenovan HPC problem. Ta problem je bil/je eden izmed glavnih katalizatorjev razvoja algebraične teorije grafov, ki je ena od najhitreje rastočih raziskovalnih področij v diskretni matematiki. Kubični TTG imajo osrednji položaj v trenutnih raziskavah tega problema, in sicer zaradi očitnega razloga: pomanjkanje povezav intuitivno otežuje iskanje poti ali ciklov, kar podpira dejstvo, da so vsi znani TTG brez hamiltonskih ciklov kubični. Cilj projekta je narediti pomemben prispevek v smeri popolne rešitve HPC problema, s posebnim poudarkom na Cayleyevih grafih. (EN) 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. |
|
Vrsta projekta Project Type |
Temeljni projekt |
|
Trajanje Duration |
01/07/2018 - 30/06/2021 |
|
URL URL |
https://www.famnit.upr.si/sl/raziskovanje/programi-in-projekti/J1-9110/ |
|
Vodja projekta Project Leader |
dr. Klavdija Kutnar |
|
Sodelujoče organizacije Participating organizations |
UL Pedagoška fakulteta; InnoRenew CoE |
|
Oddelek Department |
Oddelek za matematiko IAM |