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/