Geodesic
The number of small cycles in the Star graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 286-299.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2016_13_a57,
     author = {Alexey N. Medvedev},
     title = {The number of small cycles in the {Star} graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {286--299},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a57/}
}
TY  - JOUR
AU  - Alexey N. Medvedev
TI  - The number of small cycles in the Star graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 286
EP  - 299
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a57/
LA  - en
ID  - SEMR_2016_13_a57
ER  - 
%0 Journal Article
%A Alexey N. Medvedev
%T The number of small cycles in the Star graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 286-299
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a57/
%G en
%F SEMR_2016_13_a57
Alexey N. Medvedev. The number of small cycles in the Star graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 286-299. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a57/

[1] S. B. Akers, B. Krishnamurthy, “The star graph: an attractive alternative to n-cube”, Proceedings of International Conference on Parallel Processing, ICPP-87 (St. Charles, Illinois, August 1987), 393–400

[2] L. Wang, S. Subramanian, S. Latifi, P. K. Srimani, “Distance distribution of nodes in star graphs”, Applied Mathematics Letters, 19:8 (2006), 780–784 | MR | Zbl

[3] E. V. Konstantinova, A. N. Medvedev, “Small cycles in the Star graph”, Siberian Electronic Mathematical Reports, 11 (2014), 906–914 http://semr.math.nsc.ru/v11/p906-914.pdf | Zbl

[4] S. B. Akers, B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks”, IEEE Trans. Comput., 38:4 (1989), 555–566 | MR | Zbl

[5] J. S. Jwo, S. Lakshmivarahan, S. K. Dhall, “Embedding of cycles and grids in star graphs”, J. Circuits, Syst., Comput., 1:1 (1991), 43–74

[6] V. L. Kompel'makher, V. A. Liskovets, “Successive generation of permutations by means of a transposition basis”, Kibernetika, 3 (1975), 17–21 (in Russian) | MR | Zbl

[7] P. J. Slater, “Generating all permutations by graphical transpositions”, Ars Combinatoria, 5 (1978), 219–225 | MR | Zbl

[8] N. Alon, R. Yuster, U. Zwick, “Finding and counting given length cycles”, Algorithmica, 17:3 (1997), 209–223 | MR | Zbl

[9] J. A. Bondy, M. Siminovits, “Cycles of even length in graphs”, Journal of Combinatorial Theory B, 16 (1974), 97–105 | MR | Zbl

[10] J. A. Fill, R. Pemantle, “Percolation, First-passage Percolation and Covering Times for Richardson's Model on the N-cube”, The Annals of Applied Probability, 3:2 (1993), 593–629 | MR | Zbl

[11] E. V. Konstantinova, A. N. Medvedev, “Cycles of length seven in the Pancake graph”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 46–55 (in Russian) | MR | Zbl

[12] E. V. Konstantinova, A. N. Medvedev, “Cycles of length nine in the Pancake graph”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 33–60 (in Russian) | MR | Zbl

[13] E. Konstantinova, A. Medvedev, “Small cycles in the Pancake graph”, Ars Mathematica Contemporanea, 7 (2014), 237–246 | MR | Zbl