1. The Hamilton Compression of Highly Symmetric GraphsPetr Gregor, Arturo Merino, Torsten Mütze, 2024, original scientific article Abstract: 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.
Keywords: Hamilton cycle, Gray code, Hypercube, Permutahedron, Johnson graph, Cayley graph, Abelian group, Vertex-transitive
Published in ReVIS: 02.07.2025; Views: 41; Downloads: 0
 Full text (2,12 MB)
This document has many files! More... |
2. Graphs that admit a Hamilton path are cup-stackablePetr Gregor, Arturo Merino, Torsten Mütze, Francesco Verciani, 2025, original scientific article Abstract: Fay, Hurlbert and Tennant recently introduced a one-player game on a finite connected graph G, which they called cup stacking. Stacks of cups are placed at the vertices of G, and are transferred between vertices via stacking moves, subject to certain constraints, with the goal of stacking all cups at a single target vertex. If this is possible for every target vertex of G, then G is called stackable. In this paper, we prove that if G admits a Hamilton path, then G is stackable, which confirms several of the conjectures raised by Fay, Hurlbert and Tennant. Furthermore, we prove stackability for certain powers of bipartite graphs, and we construct graphs of arbitrarily large minimum degree and connectivity that do not allow stacking onto any of their vertices.
Keywords: Games in graphs, Hamilton path, Cartesian product
Published in ReVIS: 02.07.2025; Views: 40; Downloads: 0
Full text (778,41 KB) |
3. Combinatorial generation via permutation languages : Binary treesPetr Gregor, Torsten Mütze, Namrata, 2024, original scientific article Abstract: In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specifically, we propose algorithms for generating different classes of binary trees that are characterized by avoiding one or more of these generalized patterns. This is achieved by applying the recent Hartung–Hoang–Mütze– Williams generation framework, by encoding binary trees via permutations. In particular, we establish a one-to-one correspondence between tree patterns and certain mesh permutation patterns. We also conduct a systematic investigation of all tree patterns on at most 5 vertices, and we establish bijections between pattern-avoiding binary trees and other combinatorial objects, in particular pattern-avoiding lattice paths and set partitions.
Keywords: pattern avoidance, binary trees, mesh permutation patterns, combinatorial generation, algorithmic combinatorics
Published in ReVIS: 02.07.2025; Views: 30; Downloads: 0
Full text (1,39 MB) |
4. |
5. |
6. |
7. |
8. |
9. |
10. |
