20.500.12556/ReVIS-11892 The Hamilton Compression of Highly Symmetric Graphs We say that a Hamilton cycle in a graph G is k-symmetric, if the mapping for all, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices 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 wedge of the drawing. The maximum k for which there exists a k-symmetric Hamilton cycle in G is referred to 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 constructed cycles 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. Hamilton cycle Gray code Hypercube Permutahedron Johnson graph Cayley graph Abelian group Vertex-transitive Hamiltonov cikel Grayjeva koda Hiperkocka Permutahidron Johnsonov graf Cayleyev graf Abelova grupa ogliščno-tranzitiven true true false Angleški jezik Slovenski jezik Neznano 2025-07-02 15:32:48 2025-07-02 15:32:48 2025-07-03 03:05:40 0000-00-00 00:00:00 2024 0 0 str. 379–437 iss. 2 Vol. 28 Mar. 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-12-13 51 0218-0006 241147139 10.1007/s00026-023-00674-y https://link.springer.com/article/10.1007/s00026-023-00674-y 1 0d21e3b7-5749-11f0-8080-001a4af901a5 https://revis.openscience.si/Dokument.php?lang=slv&id=13789 s00026-023-00674-y.pdf s00026-023-00674-y.pdf 1 A946F8097294C08784D83365BDDBA115 4ff0119fb77155d348e67ab0b0f0e94e4995ccb72f155b1cc7329dcb2b0627e4 ad1c9ae8-5749-11f0-8080-001a4af901a5 https://revis.openscience.si/Dokument.php?lang=slv&id=13790 Fakulteta za informacijske študije v Novem mestu 0 0 0