Small cycles in the star graph

Elena V. Konstantinova; Alexey N. Medvedev

Small cycles in the star graph

Elena V. Konstantinova, Alexey N. Medvedev

Research output: Contribution to journal › Article › peer-review

Abstract

The Star graph is the Cayley graph on the symmetric group Symn generated by the set of transpositions f(12); (13);: :: ; (1n)g. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception 4-cycles. We characterize all distinct 6- and 8-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.

Original language	English
Pages (from-to)	906-914
Number of pages	9
Journal	Siberian Electronic Mathematical Reports
Volume	11
Publication status	Published - 3 Dec 2014
Externally published	Yes

Keywords

Cayley graphs
Cycle embedding
Product of generating elements
Star graph

Cite this

@article{c2f1e17cb75948e1b0feb380f51a2863,

title = "Small cycles in the star graph",

abstract = "The Star graph is the Cayley graph on the symmetric group Symn generated by the set of transpositions f(12); (13);: :: ; (1n)g. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception 4-cycles. We characterize all distinct 6- and 8-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.",

keywords = "Cayley graphs, Cycle embedding, Product of generating elements, Star graph",

author = "Konstantinova, {Elena V.} and Medvedev, {Alexey N.}",

year = "2014",

month = dec,

day = "3",

language = "English",

volume = "11",

pages = "906--914",

journal = "Siberian Electronic Mathematical Reports",

issn = "1813-3304",

publisher = "Sobolev Institute of Mathematics",

}

TY - JOUR

T1 - Small cycles in the star graph

AU - Konstantinova, Elena V.

AU - Medvedev, Alexey N.

PY - 2014/12/3

Y1 - 2014/12/3

N2 - The Star graph is the Cayley graph on the symmetric group Symn generated by the set of transpositions f(12); (13);: :: ; (1n)g. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception 4-cycles. We characterize all distinct 6- and 8-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.

AB - The Star graph is the Cayley graph on the symmetric group Symn generated by the set of transpositions f(12); (13);: :: ; (1n)g. These graphs are bipartite, they do not contain odd cycles but contain all even cycles with a sole exception 4-cycles. We characterize all distinct 6- and 8-cycles by their canonical forms as products of generating elements. The number of these cycles in the Star graph is also given.

KW - Cayley graphs

KW - Cycle embedding

KW - Product of generating elements

KW - Star graph

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

M3 - Article

AN - SCOPUS:84986910209

SN - 1813-3304

VL - 11

SP - 906

EP - 914

JO - Siberian Electronic Mathematical Reports

JF - Siberian Electronic Mathematical Reports

ER -

Small cycles in the star graph

Abstract

Keywords

Other files and links

Fingerprint

Cite this