Small cycles in the pancake graph

Elena Konstantinova; Alexey Medvedev

Small cycles in the pancake graph

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

Abstract

The Pancake graph is well known because of the open Pancake problem. It has the structure that any l-cycle, 6 ≤ l ≤ n!, can be embedded in the Pancake graph Pn; n ≥ 3. Recently it was shown that there are exactly n! 6 independent 6-cycles and n!(n-3) distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly n!(n ³+12n²103n+176) 16 distinct 8-cycles in P_n; n ≥ 4. A maximal set of independent 8- cycles contains n! 8 of these.

Original language	English
Pages (from-to)	237-246
Number of pages	10
Journal	Ars Mathematica Contemporanea
Volume	7
Issue number	1
Publication status	Published - 17 Jan 2014
Externally published	Yes

Keywords

Cayley graphs
Cycle embedding
Pancake graph
Small cycles

Cite this

@article{7c93d2c7599f43fca512dc068fd6062a,

title = "Small cycles in the pancake graph",

abstract = "The Pancake graph is well known because of the open Pancake problem. It has the structure that any l-cycle, 6 ≤ l ≤ n!, can be embedded in the Pancake graph Pn; n ≥ 3. Recently it was shown that there are exactly n! 6 independent 6-cycles and n!(n-3) distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly n!(n 3+12n2103n+176) 16 distinct 8-cycles in Pn; n ≥ 4. A maximal set of independent 8- cycles contains n! 8 of these.",

keywords = "Cayley graphs, Cycle embedding, Pancake graph, Small cycles",

author = "Elena Konstantinova and Alexey Medvedev",

year = "2014",

month = jan,

day = "17",

language = "English",

volume = "7",

pages = "237--246",

journal = "Ars Mathematica Contemporanea",

issn = "1855-3966",

publisher = "Society of Mathematicians, Physicists and Astronomers of Slovenia",

number = "1",

}

TY - JOUR

T1 - Small cycles in the pancake graph

AU - Konstantinova, Elena

AU - Medvedev, Alexey

PY - 2014/1/17

Y1 - 2014/1/17

N2 - The Pancake graph is well known because of the open Pancake problem. It has the structure that any l-cycle, 6 ≤ l ≤ n!, can be embedded in the Pancake graph Pn; n ≥ 3. Recently it was shown that there are exactly n! 6 independent 6-cycles and n!(n-3) distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly n!(n 3+12n2103n+176) 16 distinct 8-cycles in Pn; n ≥ 4. A maximal set of independent 8- cycles contains n! 8 of these.

AB - The Pancake graph is well known because of the open Pancake problem. It has the structure that any l-cycle, 6 ≤ l ≤ n!, can be embedded in the Pancake graph Pn; n ≥ 3. Recently it was shown that there are exactly n! 6 independent 6-cycles and n!(n-3) distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly n!(n 3+12n2103n+176) 16 distinct 8-cycles in Pn; n ≥ 4. A maximal set of independent 8- cycles contains n! 8 of these.

KW - Cayley graphs

KW - Cycle embedding

KW - Pancake graph

KW - Small cycles

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

M3 - Article

AN - SCOPUS:84892145532

SN - 1855-3966

VL - 7

SP - 237

EP - 246

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

IS - 1

ER -

Small cycles in the pancake graph

Abstract

Keywords

Other files and links

Fingerprint

Cite this