Abstract:We present an algorithm for computing Hamiltonian cycles that are invariant under a graph automorphism acting on them as a rotation. We also present an application of this algorithm for computing the Hamiltonian compression factor of a graph, that is, the largest order of an automorphism preserving some Hamiltonian cycle and acting on it as a rotation. As an example, we compute the Hamiltonian compression factors of all cubic edge-transitive graphs on up to $10{,}000$ vertices, with the exception of two graphs, which are not Hamiltonian, and $98$ graphs (the smallest having $2304$ vertices) for which only a lower bound for the compression factor is given. As a byproduct, we obtain shortest LCF codes for each of these graphs (except for the two non-Hamiltonian ones; for the $98$ unresolved graphs, the codes obtained are the shortest among those we found).
From: Primož Potočnik [view email]
[v1]
Sat, 20 Jun 2026 08:16:25 UTC (82 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。