Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph

The Bubble-sort graph \(BS_n,\,n\geqslant 2\), is a Cayley graph over the symmetric group \(Sym_n\) generated by transpositions from the set \(\{(1 2), (2 3),\ldots, (n-1 n)\}\). It is a bipartite graph containing all even cycles of length \(\ell\), where \(4\leqslant \ell\leqslant n!\). We give an...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-04
Main Authors: Konstantinova, Elena V, Medvedev, Alexey N
Format: Article
Language:English
Subjects:
Bubbles
Canonical forms
Traveling salesman problem
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Bubble-sort graph \(BS_n,\,n\geqslant 2\), is a Cayley graph over the symmetric group \(Sym_n\) generated by transpositions from the set \(\{(1 2), (2 3),\ldots, (n-1 n)\}\). It is a bipartite graph containing all even cycles of length \(\ell\), where \(4\leqslant \ell\leqslant n!\). We give an explicit combinatorial characterization of all its \(4\)- and \(6\)-cycles. Based on this characterization, we define generalized prisms in \(BS_n,\,n\geqslant 5\), and present a new approach to construct a Hamiltonian cycle based on these generalized prisms.
ISSN:2331-8422
DOI:10.48550/arxiv.1901.03917