Department Colloquium

Location: RI 208

Speaker: Sarobidy Razafimahatratra, Fields Institute for Research in Mathematical Sciences

Title:  The Hamilton compression of vertex-transitive graphs of order \(pq\)

Abstract:

Given a graph \(X = (V, E)\), a Hamilton path (cycle) of \(X\) is a path (cycle) that contains all vertices of \(X\). For any integer \(k \geq 1\) and a Hamilton cycle \(C = v_0 v_1 \ldots v_{n−1} v_0\) of \(X\), we say that \(C\) is \(k\)-symmetric if the map \(\phi_k : V \rightarrow V\) such that \(\phi_k(v_i) = v_i+ n/k\), for \( 0 ≤ i ≤ n − 1\), where the indices are taken modulo \(n\), is an automorphism of \(X\). We define \(\kappa(X, C)\) to be the largest \(k\) such that \(C\) is a \(k\)-symmetric Hamilton cycle of \(X\). The Hamilton compression of \(X\) is the parameter

\[\kappa(X) := max \{\kappa(X, C) : C \mbox{ is a Hamilton cycle of } X\}.\]

In 1969, Lovasz asked whether every vertex-transitive graphs admits a Hamilton path. To this day, this question is still wide open. When this question is rephrased to be about Hamilton cycles however, there are five known vertex-transitive graphs that do not admit such cycles. Determining whether or not these five graphs are the only vertex-transitive graphs without Hamilton cycles is one of the longstanding problems in algebraic graph theory.

In 2021, Du, Kutnar, and Marusic showed that vertex-transitive graphs of order a product of two distinct primes admit a Hamilton cycle. In this talk, we will determine the Hamilton compression of certain vertex-transitive graphs of order \(pq\), where \(p\) and \(q\) are distinct primes.