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

Elena V. Konstantinova, Alexey N. Medvedev

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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.

Язык оригиналаанглийский
Номер статьи106094
ЖурналInformation Processing Letters
Том168
DOI
СостояниеОпубликовано - июн 2021

Fingerprint Подробные сведения о темах исследования «Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать