Аннотация:
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.