A numeral system for the middle-levels graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2010
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929454371045376 |
|---|---|
| author | Dejter, Italo J. |
| author_facet | Dejter, Italo J. |
| contents | 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 $\rightarrow$DFS by: {\bf(i)} ($\leftarrow$BFS-assigned) Kierstead-Trotter lexical colors $0,\ldots,k$ for the descending nodes; {\bf(ii)} asterisks $*$ for the $k$ ascending edges. Two ways of corresponding a restricted-growth $k$-string $α$ to each $T$ exist, namely one Stanley's way and a novel way that assigns $F(T)$ to $α$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1012_0995 |
| institution | arXiv |
| publishDate | 2010 |
| record_format | arxiv |
| spellingShingle | A numeral system for the middle-levels graphs Dejter, Italo J. Combinatorics 06A05, 94B25, 05C62, 05C75, 05C69, 05C45 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 $\rightarrow$DFS by: {\bf(i)} ($\leftarrow$BFS-assigned) Kierstead-Trotter lexical colors $0,\ldots,k$ for the descending nodes; {\bf(ii)} asterisks $*$ for the $k$ ascending edges. Two ways of corresponding a restricted-growth $k$-string $α$ to each $T$ exist, namely one Stanley's way and a novel way that assigns $F(T)$ to $α$ 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. |
| title | A numeral system for the middle-levels graphs |
| topic | Combinatorics 06A05, 94B25, 05C62, 05C75, 05C69, 05C45 |
| url | https://arxiv.org/abs/1012.0995 |