Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph
(2021) Information Processing Letters — Vol. 168, p. 106094 (2021)
Files
Medvedev_ICTM.pdf
Open Access - Adobe PDF
- 890.47 KB
Details
- Authors
Konstantinova, Elena V. 
Medvedev, Alexey
- Abstract
- The Bubble-sort graph BSn,n⩾2, is a Cayley graph over the symmetric group Symn generated by transpositions from the set {(12),(23),…,(n−1n)}. It is a bipartite graph containing all even cycles of length ℓ, where 4⩽ℓ⩽n!. We give an explicit combinatorial characterization of all its 4- and 6-cycles. Based on this characterization, we define generalized prisms in BSn,n⩾5, and present a new approach to construct a Hamiltonian cycle based on these generalized prisms.
- Affiliations
Citations
Konstantinova, E. V., & Medvedev, A. (2021). Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph. Information Processing Letters, 168, 106094. https://doi.org/10.1016/j.ipl.2021.106094 (Original work published 2021)