RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2014, том 11, страницы 906–914 (Mi semr535)

Эта публикация цитируется в 3 статьях

Дискретная математика и математическая кибернетика

Small cycles in the star graph

Elena V. Konstantinovaab, Alexey N. Medvedevac

a Sobolev Institute of Mathematics, 4, Koptyug av., 630090, Novosibirsk, Russia
b Novosibisk State University, 2, Pirogova st., 630090, Novosibirsk, Russia
c Central European University, Nador ut. 9, Budapest, 1051, Hungary

Аннотация: The Star graph is the Cayley graph on the symmetric group $Sym_n$ generated by the set of transpositions $\{(1 2),(1 3),\ldots,(1 n)\}$. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception $4$-cycles. We characterize all distinct $6$- and $8$-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.

Ключевые слова: Cayley graphs; Star graph; cycle embedding; product of generating elements.

УДК: 519.1

MSC: 05C25

Поступила 15 октября 2014 г., опубликована 3 декабря 2014 г.

Язык публикации: английский



© МИАН, 2024