Basic Research Project J1-50000
Hamilton cycles with rotational symmetry in connected vertex-transitivity graphs

 

Project Title: Hamilton cycles with rotational symmetry in connected vertex-transitivity graphs

PI: Dragan Marušič

Project Code: J1-50000

Type of the Project: basic research project.

Funding Organization: Slovenian Research and Innovation Agency (ARIS).

Research Field (ARRS): 1.01.00 - Natural Sciences and Mathematics / Mathematics.

Duration: 1. 10. 2023 - 30. 9. 2026.

Project Category: B.

Yearly Range: 1.35 FTE (2.294 research hours).

Sicris profile of the project is avaliable here.

Research Organizations:
Univerza na Primorskem, Inštitut Andrej Marušič
Univerza v Ljubljani, Pedagoška fakulteta
InnoRenew CoE

Project Members:

Dragan Marušič (ARIS code 02887)

Istvan Kovacs (ARIS code 25997)

Klavdija Kutnar (ARIS code 24997)

Edward Tauscher Dobson (ARIS code 34109)

Russell Stephen Woodroofe (ARIS code 50355)

Štefko Miklavič (ARIS code 21656)

Ademir Hujdurović (ARIS code 32518)

Sarobidy Razafimahatratra Andriaherimanana (ARIS code 56940)

Blas Fernandez (ARIS code 52892)

Draženka Višnjić (ARIS code 55934)

Gregory Caldwel Robson (ARIS code 54873)

Michel Lavrauw (ARIS code 57308)

Marko Orel (ARIS code 25610)

Bojan Kuzma (ARIS code 18893)

Michael Mrissa (ARIS code 51811)

Balazs David (ARIS code 51616)

Primož Šparl (ARIS code 23341)

Aleksander Malnič (ARIS code 02507)

Abstract:

Motivated by recently introduced graph parameter that quantifies how symmetric a Hamilton cycle in a graph can be the proposed project considers symmetries of Hamilton cycles in connected vertex-transitive graphs. The parameter was introduced in 2022 by Gregor, Merino and Muetze. Formally, let X be a graph with n vertices. We say that a Hamilton cycle C=(v0,...,vn-1) is k-symmetric if the mapping f: V(X) -> V(X) defined by f(vi)=vi+n/k for all i=0,...,n-1, where indices are considered modulo n, is an automorphism of X. In this case we have

C=(P,f (P), f 2(P),...,f k-1(P)) for the path P=v0,...,vn/k-1.

Therefore the entire cycle C can be reconstructed from the path P, which contains only a 1/k-fraction of all the vertices, by repeatedly applying the automorphism f to it. If we lay out the vertices equidistantly on a circle, and draw edges of X as straight lines, then we obtain a drawing of X with k-fold rotational symmetry, that is, f is a rotation by 360/k degrees. The maximum k for which the Hamilton cycle C of X is k-symmetric is called the compression factor of C and is denoted by kappa(X,C). For a graph X we define kappa(X)=max{kappa(X,C) | C is a Hamilton cycle in X}, and we refer to this quantity as the Hamilton compression of X. If X has no Hamilton cycle, then we define k(X)=0. The quantity kappa(X) can be therefore seen as a measure for the nicest (that is, the most symmetric) way of drawing the graph X on a circle.

The main object of the project is to study Hamilton compression of connected vertex-transitive graphs, those for which the existence of Hamilton cycles is already known, and in view of the connection with the polycirculant conjecture, also those for which no information on Hamilton cycles has been obtained thus far. In this sense the proposed project has a clear link to the Lovasz hamiltonicity problem for vertex-transitive graphs.