The Hamilton Compression of Highly Symmetric Graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10450700" target="_blank" >RIV/00216208:11320/22:10450700 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.4230/LIPIcs.MFCS.2022.54" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2022.54</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2022.54" target="_blank" >10.4230/LIPIcs.MFCS.2022.54</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The Hamilton Compression of Highly Symmetric Graphs
Popis výsledku v původním jazyce
We say that a Hamilton cycle C = (x1,...,xn) in a graph G is k-symmetric, if the mapping xi RIGHTWARDS ARROW xi+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 x1,...,xn 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.
Název v anglickém jazyce
The Hamilton Compression of Highly Symmetric Graphs
Popis výsledku anglicky
We say that a Hamilton cycle C = (x1,...,xn) in a graph G is k-symmetric, if the mapping xi RIGHTWARDS ARROW xi+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 x1,...,xn 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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA22-15272S" target="_blank" >GA22-15272S: Principy kombinatorického generování</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-256-3
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
14
Strana od-do
1-14
Název nakladatele
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Místo vydání
Dagstuhl, Německo
Místo konání akce
Vienna
Datum konání akce
22. 8. 2022
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—