The Hamilton compression of highly symmetric graphs

DOI10.1007/S00026-023-00674-YarXiv2205.08126OpenAlexW4389669716MaRDI QIDQ6399331FDOQ6399331

Petr Gregor, Torsten Mütze, Arturo I. Merino

Publication date: 17 May 2022

Abstract: We say that a Hamilton cycle $C=(x_1,ldots,x_n)$ in a graph $G$ is $k$-symmetric, if the mapping $x_{i}mapsto{x}_{i+n/k}$ for all $i=1,ldots,n$, where indices are considered modulo $n$, is an automorphism of $G$. In other words, if we lay out the vertices $x_1,ldots,x_n$ equidistantly on a circle and draw the edges of $G$ as straight lines, then the drawing of $G$ has $k$-fold rotational symmetry, i.e., all information about the graph is compressed into a $360^{c}irc/k$ wedge of the drawing. We refer to the maximum $k$ for which there exists a $k$-symmetric Hamilton cycle in $G$ as the Hamilton compression of $G$. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.

Full work available at URL: https://doi.org/10.1007/s00026-023-00674-y

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Linear codes (general theory) (94B05) Graph theory (05C99)

Cited In (1)

• Infinite families of vertex-transitive graphs with prescribed Hamilton compression

This page was built for publication: The Hamilton compression of highly symmetric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399331)