Greedy cycles in the star graphs

Dmitriy Aleksandrovich Gostevsky, Elena Valentinovna Konstantinova

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)205-213
Number of pages9
JournalСибирские электронные математические известия
Volume15
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Cayley graph
  • Greedy cycle
  • Greedy sequence
  • Star graph
  • greedy sequence
  • greedy cycle

OECD FOS+WOS

  • 1.01 MATHEMATICS

Fingerprint Dive into the research topics of 'Greedy cycles in the star graphs'. Together they form a unique fingerprint.

Cite this