The number of small cycles in the star graph

Research output: Contribution to journalArticlepeer-review

Abstract

The Star graph is the Cayley graph on the symmetric group Symn generated by the set of transpositions ((1 i) ε Symn: 2 ≤ i ≤ n). This graph is bipartite and does not contain odd cycles but contains all even cycles with a sole exception of 4-cycles. We denote as (π, id)-cycles the cycles constructed from two shortest paths between a given vertex π and the identity id. In this paper we derive the exact number of (π, id)- cycles for particular structures of the vertex π. We use these results to obtain the total number of 10-cycles passing through any given vertex in the Star graph.

Original languageEnglish
Pages (from-to)286-299
Number of pages14
JournalSiberian Electronic Mathematical Reports
Volume13
Issue number1
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • Cayley graphs
  • Cycle embedding
  • Number of cycles
  • Star graph

Fingerprint

Dive into the research topics of 'The number of small cycles in the star graph'. Together they form a unique fingerprint.

Cite this