A numeral system for the middle-levels graphs

Abstract

The middle-levels graph $M_k$ ($0<k\in \mathbb{Z}$) has a dihedral quotient pseudograph $R_k$ whose vertices are the $k$-edge ordered trees $T$, each $T$ encoded as a $(2k+1)$-string $F(T)$ formed via $\to$DFS by: {\bf(i)} ($\leftarrow$BFS-assigned) Kierstead-Trotter lexical colors $0,\dots ,k$ for the descending nodes; {\bf(ii)} asterisks $\ast$ for the $k$ ascending edges. Two ways of corresponding a restricted-growth $k$-string $\alpha$ to each $T$ exist, namely one Stanley's way and a novel way that assigns $F(T)$ to $\alpha$ via nested substring-swaps. These swaps permit to sort $V(R_k)$ as an ordered tree that allows a lexical visualization of $M_k$ as well as the Hamilton cycles of $M_k$ constructed by P. Gregor, T. Mütze and J. Nummenpalo.

arXiv comment26 pages, 8 figures, 10 tables