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 language | English |
---|---|
Pages (from-to) | 286-299 |
Number of pages | 14 |
Journal | Siberian Electronic Mathematical Reports |
Volume | 13 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2016 |
Externally published | Yes |
Keywords
- Cayley graphs
- Cycle embedding
- Number of cycles
- Star graph