The Hamilton Compression of Highly Symmetric Graphs

Authors Petr Gregor , Arturo Merino , Torsten Mütze



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.54.pdf
  • Filesize: 1.65 MB
  • 14 pages

Document Identifiers

Author Details

Petr Gregor
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
Arturo Merino
  • Department of Mathematics, TU Berlin, Germany
Torsten Mütze
  • Department of Computer Science, University of Warwick, United Kingdom
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic

Acknowledgements

We thank Fedor Petrov and Michal Koucký for ideas that simplified some proofs in the full version. We also thank the reviewers for their helpful comments.

Cite AsGet BibTex

Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.54

Abstract

We say that a Hamilton cycle C = (x₁,…,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁,…,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^∘/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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Combinatorics
Keywords
  • Hamilton cycle
  • Gray code
  • hypercube
  • permutahedron
  • Johnson graph
  • Cayley graph
  • abelian group
  • vertex-transitive

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. B. Alspach. Lifting Hamilton cycles of quotient graphs. Discrete Math., 78(1-2):25-36, 1989. URL: https://doi.org/10.1016/0012-365X(89)90157-X.
  2. D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006. Google Scholar
  3. G. S. Bhat and C. D. Savage. Balanced Gray codes. Electron. J. Combin., 3(1):Paper 25, 11 pp., 1996. URL: http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html.
  4. C. C. Chen and N. F. Quimpo. On strongly Hamiltonian abelian group graphs. In Combinatorial mathematics, VIII (Geelong, 1980), volume 884 of Lecture Notes in Math., pages 23-34. Springer, Berlin-New York, 1981. Google Scholar
  5. S. J. Curran and J. A. Gallian. Hamiltonian cycles and paths in Cayley graphs and digraphs - A survey. Discrete Math., 156(1-3):1-18, 1996. URL: https://doi.org/10.1016/0012-365X(95)00072-5.
  6. S. Du, K. Kutnar, and D. Marušič. Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes. Combinatorica, 41(4):507-543, 2021. URL: https://doi.org/10.1007/s00493-020-4384-6.
  7. T. Etzion and K. G. Paterson. Near optimal single-track Gray codes. IEEE Trans. Inform. Theory, 42(3):779-789, 1996. URL: https://doi.org/10.1109/18.490544.
  8. S. Felsner, L. Kleist, T. Mütze, and L. Sering. Rainbow cycles in flip graphs. SIAM J. Discrete Math., 34(1):1-39, 2020. URL: https://doi.org/10.1137/18M1216456.
  9. R. Frucht. A canonical representation of trivalent Hamiltonian graphs. J. Graph Theory, 1(1):45-60, 1977. URL: https://doi.org/10.1002/jgt.3190010111.
  10. M. R. Garey and D. S. Johnson. Computers and intractability. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. Google Scholar
  11. R. J. Gould. Updating the Hamiltonian problem - A survey. J. Graph Theory, 15(2):121-157, 1991. URL: https://doi.org/10.1002/jgt.3190150204.
  12. R. J. Gould. Advances on the Hamiltonian problem - A survey. Graphs Combin., 19(1):7-52, 2003. URL: https://doi.org/10.1007/s00373-002-0492-x.
  13. R. J. Gould. Recent advances on the Hamiltonian problem: Survey III. Graphs Combin., 30(1):1-46, 2014. URL: https://doi.org/10.1007/s00373-013-1377-x.
  14. F. Gray. Pulse code communication, 1953. March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058. Google Scholar
  15. P. Gregor, A. Merino, and T. Mütze. The Hamilton compression of highly symmetric graphs. Full preprint version of the present article, 2022. URL: http://arxiv.org/abs/2205.08126.
  16. A. P. Hiltgen, K. G. Paterson, and M. Brandestini. Single-track gray codes. IEEE Trans. Inf. Theory, 42(5):1555-1561, 1996. URL: https://doi.org/10.1109/18.532900.
  17. D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011. Google Scholar
  18. D. Kühn and D. Osthus. A survey on Hamilton cycles in directed graphs. European J. Combin., 33(5):750-766, 2012. URL: https://doi.org/10.1016/j.ejc.2011.09.030.
  19. K. Kutnar and D. Marušič. Hamilton cycles and paths in vertex-transitive graphs - Current directions. Discrete Math., 309(17):5491-5500, 2009. URL: https://doi.org/10.1016/j.disc.2009.02.017.
  20. L. Lovász. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, AB, 1969). Gordon and Breach, New York, 1970. Google Scholar
  21. A. I. Merino, O. Mička, and T. Mütze. On a combinatorial generation problem of Knuth. In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 735-743. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.46.
  22. T. Mütze. Combinatorial Gray codes - An updated survey, 2022. URL: http://arxiv.org/abs/2202.01280.
  23. T. Mütze, J. Nummenpalo, and B. Walczak. Sparse Kneser graphs are Hamiltonian. J. Lond. Math. Soc. (2), 103(4):1253-1275, 2021. URL: https://doi.org/10.1112/jlms.12406.
  24. I. Pak and R. Radoičić. Hamiltonian paths in Cayley graphs. Discrete Math., 309(17):5501-5508, 2009. URL: https://doi.org/10.1016/j.disc.2009.02.018.
  25. C. D. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: https://doi.org/10.1137/S0036144595295272.
  26. M. Schwartz and T. Etzion. The structure of single-track Gray codes. IEEE Trans. Inform. Theory, 45(7):2383-2396, 1999. URL: https://doi.org/10.1109/18.796379.
  27. I. Shields, B. Shields, and C. D. Savage. An update on the middle levels problem. Discrete Math., 309(17):5271-5277, 2009. URL: https://doi.org/10.1016/j.disc.2007.11.010.
  28. D. Witte and J. A. Gallian. A survey: Hamiltonian cycles in Cayley graphs. Discrete Math., 51(3):293-304, 1984. URL: https://doi.org/10.1016/0012-365X(84)90010-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail