Seminario de Grafos
Speaker: Arturo Merino, Technische Universität Berlin, Alemania.
Title: The Hamilton Compression of Highly Symmetric Graphs.
Abstract:
The relationship between symmetry and Hamiltonicity in graphs has gained much attention in recent years but is still not so well understood, this can be seen, for example, in the colliding conjectures of Lovász and Babai.
To try to shed some light on this relationship, we introduce a measure of how symmetric the Hamilton cycles in a graph can be.
We say that a Hamilton cycle C=x_1,…,x_n in a graph is k-symmetric, if the mapping x_i to 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_1,…,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 particularly nice properties like having few tracks and/or being balanced.
Preprint available on arXiv:2205.08126.
Jueves 10 de Noviembre del 2022, de 10.30-11:45 hrs.
Sala de Seminarios Jacques L Lions, CMM, Séptimo Piso Torre Norte.