Discrete mathematics and mathematical cybernetics

The number of small cycles in the Star graph

Alexey N. Medvedev<sup>abc

a</sup> 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

Abstract: 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.

Keywords: Cayley graphs; Star graph; cycle embedding; number of cycles.

UDC: 519.1

MSC: 05C25

Received January 21, 2016, published April 29, 2016

Language: English

DOI: 10.17377/semi.2016.13.023

Bibliographic databases:

•