TY - JOUR

T1 - Greedy cycles in the star graphs

AU - Gostevsky, Dmitriy Aleksandrovich

AU - Konstantinova, Elena Valentinovna

N1 - Publisher Copyright: © 2018 Sobolev Institute of Mathematics. Copyright: Copyright 2019 Elsevier B.V., All rights reserved. Publisher Copyright: © 2018 Sobolev Institute of Mathematics.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We apply the greedy approach to construct greedy cycles in Star graphs Sn, n ≥ 3, defined as Cayley graphs on the symmetric group Symn with generating set t = [(1 i), 2 ≤ i ≤ n] of transpositions. We define greedy sequences presented by distinct elements from t, and prove that any greedy sequence of length k, 2 ≤ k ≤ n - 1, forms a greedy cycle of length 2 · 3k-1. Based on these greedy sequences we give a construction of a maximal set of independent greedy cycles in the Star graphs Sn for any n ≥ 3.

AB - We apply the greedy approach to construct greedy cycles in Star graphs Sn, n ≥ 3, defined as Cayley graphs on the symmetric group Symn with generating set t = [(1 i), 2 ≤ i ≤ n] of transpositions. We define greedy sequences presented by distinct elements from t, and prove that any greedy sequence of length k, 2 ≤ k ≤ n - 1, forms a greedy cycle of length 2 · 3k-1. Based on these greedy sequences we give a construction of a maximal set of independent greedy cycles in the Star graphs Sn for any n ≥ 3.

KW - Cayley graph

KW - Greedy cycle

KW - Greedy sequence

KW - Star graph

KW - greedy sequence

KW - greedy cycle

UR - http://www.scopus.com/inward/record.url?scp=85070231280&partnerID=8YFLogxK

U2 - 10.17377/semi.2018.15.020

DO - 10.17377/semi.2018.15.020

M3 - Article

AN - SCOPUS:85070231280

VL - 15

SP - 205

EP - 213

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

ER -