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.
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА