|
Discrete mathematics and mathematical cybernetics
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
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.
Received January 21, 2016, published April 29, 2016
Citation:
Alexey N. Medvedev, “The number of small cycles in the Star graph”, Sib. Èlektron. Mat. Izv., 13 (2016), 286–299
Linking options:
https://www.mathnet.ru/eng/semr672 https://www.mathnet.ru/eng/semr/v13/p286
|
Statistics & downloads: |
Abstract page: | 216 | Full-text PDF : | 61 | References: | 32 |
|