Standard

Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph. / Konstantinova, Elena V.; Medvedev, Alexey N.

In: Information Processing Letters, Vol. 168, 106094, 06.2021.

Research output: Contribution to journal › Article › peer-review

Harvard

Konstantinova, EV & Medvedev, AN 2021, 'Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph', Information Processing Letters, vol. 168, 106094. https://doi.org/10.1016/j.ipl.2021.106094

APA

Konstantinova, E. V., & Medvedev, A. N. (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

Vancouver

Konstantinova EV, Medvedev AN. Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph. Information Processing Letters. 2021 Jun;168:106094. doi: 10.1016/j.ipl.2021.106094

Author

Konstantinova, Elena V. ; Medvedev, Alexey N. / Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph. In: Information Processing Letters. 2021 ; Vol. 168.

BibTeX

@article{8c063afc5c454951b7a28ad61f1c3a7d,
title = "Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph",
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.",
keywords = "Bubble-sort graph, Cayley graph, Generalized prisms, Hamiltonian cycle, Johnson graph",
author = "Konstantinova, {Elena V.} and Medvedev, {Alexey N.}",
note = "Funding Information: The authors thank Zahary Hamaker for referring us to permutahedra, which have direct relation to the graph under our consideration and Valeriy Bardakov for providing insights regarding permutahedra. We thank the anonymous reviewers for their valuable suggestions that helped to improve the quality of the manuscript. This work was supported partially by the grants 17-51-560008 , 18-01-00353 and 19-01-00682 of the Russian Foundation for Basic Research . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
month = jun,
doi = "10.1016/j.ipl.2021.106094",
language = "English",
volume = "168",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",

}

RIS

TY - JOUR

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

AU - Konstantinova, Elena V.

AU - Medvedev, Alexey N.

N1 - Funding Information: The authors thank Zahary Hamaker for referring us to permutahedra, which have direct relation to the graph under our consideration and Valeriy Bardakov for providing insights regarding permutahedra. We thank the anonymous reviewers for their valuable suggestions that helped to improve the quality of the manuscript. This work was supported partially by the grants 17-51-560008 , 18-01-00353 and 19-01-00682 of the Russian Foundation for Basic Research . Publisher Copyright: © 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/6

Y1 - 2021/6

N2 - 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.

AB - 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.

KW - Bubble-sort graph

KW - Cayley graph

KW - Generalized prisms

KW - Hamiltonian cycle

KW - Johnson graph

UR - http://www.scopus.com/inward/record.url?scp=85099398231&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2021.106094

DO - 10.1016/j.ipl.2021.106094

M3 - Article

AN - SCOPUS:85099398231

VL - 168

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 106094

ER -

ID: 27487261