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

Сиб. электрон. матем. изв., 2016, том 13, страницы 286–299 (Mi semr672)

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

The number of small cycles in the Star graph

Alexey N. Medvedevabc

a Sobolev Institute of Mathematics, 4, Koptyug av., 630090, Novosibirsk, Russia
b MTA Rényi Alfréd Institute of Mathematics, Reáltanoda ut. 13-15., Budapest, 1053, Hungary
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\,i) \in Sym_n: 2 \leqslant i \leqslant n\}$. This graph is bipartite and does not contain odd cycles but contains all even cycles with a sole exception of $4$-cycles. We denote as $(\pi,id)$-cycles the cycles constructed from two shortest paths between a given vertex $\pi$ and the identity $id$. In this paper we derive the exact number of $(\pi,id)$-cycles for particular structures of the vertex $\pi$. We use these results to obtain the total number of $10$-cycles passing through any given vertex in the Star graph.

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

УДК: 519.1

MSC: 05C25

Поступила 21 января 2016 г., опубликована 29 апреля 2016 г.

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

DOI: 10.17377/semi.2016.13.023



Реферативные базы данных:


© МИАН, 2024