Geodesic
Small cycles in the star graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 906-914.

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 2),(1 3),\ldots,(1 n)\}$. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception $4$-cycles. We characterize all distinct $6$- and $8$-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.
Keywords: Cayley graphs; Star graph; cycle embedding; product of generating elements. 
@article{SEMR_2014_11_a55,
     author = {Elena V. Konstantinova and Alexey N. Medvedev},
     title = {Small cycles in the star graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {906--914},
     publisher = {mathdoc},
     volume = {11},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a55/}
}
TY  - JOUR
AU  - Elena V. Konstantinova
AU  - Alexey N. Medvedev
TI  - Small cycles in the star graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 906
EP  - 914
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a55/
LA  - en
ID  - SEMR_2014_11_a55
ER  - 
%0 Journal Article
%A Elena V. Konstantinova
%A Alexey N. Medvedev
%T Small cycles in the star graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 906-914
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a55/
%G en
%F SEMR_2014_11_a55
Elena V. Konstantinova; Alexey N. Medvedev. Small cycles in the star graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 906-914. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a55/

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

[2] I. J. Dejter, O. Serra, “Efficient dominating sets in Cayley graphs”, Discrete Applied Mathematics, 129 (2003), 319–328 | DOI | MR | Zbl

[3] 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 | DOI

[4] E. Konstantinova, “On some structural properties of Star and Pancake graphs”, LNCS, 7777, 2013, 472–487 | MR | Zbl

[5] E. V. Konstantinova, A. N. Medvedev, “Cycles of length seven in the Pancake graph”, Diskretnyi Analiz i Issledovanie Operatsii, 17 (2010), 46–55 (in Russian) | MR | Zbl

[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

[7] Ke Qiu, “Optimal broadcasting algorithm for multiple messages on the star and pancake graphs using minimum dominating sets”, Congressus nomerantium, 181 (2006), 33–39 | MR | Zbl

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