Geodesic
Greedy cycles in the star graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 205-213.

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

We apply the greedy approach to construct greedy cycles in Star graphs $S_n, n\geqslant 3,$ defined as Cayley graphs on the symmetric group $\mathrm{Sym}_n$ with generating set $t=\{(1\,i),2\leqslant i\leqslant n\}$ of transpositions. We define greedy sequences presented by distinct elements from $t$, and prove that any greedy sequence of length $k$, $2\leqslant k\leqslant n-1$, forms a greedy cycle of length $2\cdot3^{k-1}$. Based on these greedy sequences we give a construction of a maximal set of independent greedy cycles in the Star graphs $S_n$ for any $n\geqslant 3$.
Keywords: Cayley graph; Star graph; greedy sequence; greedy cycle. 
@article{SEMR_2018_15_a62,
     author = {D. A. Gostevsky and E. V. Konstantinova},
     title = {Greedy cycles in the star graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {205--213},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a62/}
}
TY  - JOUR
AU  - D. A. Gostevsky
AU  - E. V. Konstantinova
TI  - Greedy cycles in the star graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 205
EP  - 213
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a62/
LA  - en
ID  - SEMR_2018_15_a62
ER  - 
%0 Journal Article
%A D. A. Gostevsky
%A E. V. Konstantinova
%T Greedy cycles in the star graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 205-213
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a62/
%G en
%F SEMR_2018_15_a62
D. A. Gostevsky; E. V. Konstantinova. Greedy cycles in the star graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 205-213. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a62/

[1] J. Akiyama, M. Kano, Factors and factorizations of graphs. Proof techniques in factor theory, Lecture Notes in Mathematics, 2031, Springer, 2011 | DOI | MR | Zbl

[2] J.S. Jwo, S. Lakshmivarahan, S.K. Dhall, “Embedding of cycles and grids in star graphs”, J. Circuits Syst. Comput., 1 (1991), 43–47 | DOI | MR

[3] R. Hassin, Sh. Rubinstein, “On the complexity of the $k$-customer vehicle routing problem”, Oper. Res. Lett., 33:1 (2005), 71–76 | DOI | MR | Zbl

[4] M.C. Heydemann, “Cayley graphs as interconnection networks”, Graph symmetry: algebraic methods and applications, eds. G. Hahn, G. Sabidussi, 1997, 167–224 | DOI | MR | Zbl

[5] E.V. Konstantinova, A.N. Medvedev, “Small cycles in Star graph”, Siberian Electronic Mathematical Reports, 11 (2014), 906–914 | MR | Zbl

[6] E. Konstantinova, A. Medvedev, “Independent even cycles in the Pancake graph and greedy Prefix-reversal Gray codes”, Graphs Comb., 32:5 (2016), 1965–1978 | DOI | MR | Zbl

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

[8] L. Lovász, M. D. Plummer, Matching Theory, North-Holland Mathematics Studies, 121, Elsevier, 1986 | MR | Zbl

[9] L. Sunil Chandran, L. Shankar Ram, “On the relationship between ATSP and the cycle cover problem”, Theor. Comput. Sci., 370:1–3 (2007), 218–228 | DOI | MR | Zbl

[10] A. Williams, “The greedy gray code algorithm”, Lecture Notes in Computer Science, 8037, 2013, 525–536 | DOI | MR | Zbl

[11] A. Williams, J. Sawada, “Greedy Pancake Flipping”, Electronic Notes in Discrete Mathematics, 44 (2013), 357–362 | DOI

[12] S. Zaks, “A new algorithm for generation of permutations”, BIT Numerical Mathematics, 24:2 (1984), 196–204 | DOI | MR | Zbl