Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph | Sciact - Система учета научной деятельности ИМ СО РАН

Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph Научная публикация

Журнал

Information Processing Letters
ISSN: 0020-0190

Вых. Данные

Год: 2021, Том: 168, Номер статьи : 106094, Страниц : DOI: 10.1016/j.ipl.2021.106094

Ключевые слова

Bubble-sort graph; Cayley graph; Generalized prisms; Hamiltonian cycle; Johnson graph

Авторы

Konstantinova E.V. ^1,2 , Medvedev A.N. ³

Организации

1	Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russian Federation
2	Novosibisk State University, Pirogova str. 2, Novosibirsk, 630090, Russian Federation
3	ICTEAM, Université catholique de Louvain, Louvain-la-Neuve, Belgium

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. © 2021 Elsevier B.V.

Konstantinova E.V. , Medvedev A.N.
Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph
Information Processing Letters. 2021. V.168. 106094 . DOI: 10.1016/j.ipl.2021.106094 WOS Scopus OpenAlex

Web of science:	WOS:000624438100003
Scopus:	2-s2.0-85099398231
OpenAlex:	W2938350870

БД	Цитирований
Scopus	7
OpenAlex	7
Web of science	7