期刊
DISCRETE APPLIED MATHEMATICS
卷 271, 期 -, 页码 1-14出版社
ELSEVIER
DOI: 10.1016/j.dam.2019.08.008
关键词
Burnt pancake graph; Cayley graphs; Hamiltonian cycles; Weakly pancyclic
资金
- Indiana University's Global Talent Attraction Program
The pancake graph P-n is the Cayley graph of the symmetric group S-n on n elements generated by prefix reversals. P-n has been shown to have properties that makes it a useful network scheme for parallel processors. For example, it is (n - 1)-regular, vertex-transitive, and one can embed cycles in it of length l with 6 <= l <= n!. The burnt pancake graph BPn, which is the Cayley graph of the group of signed permutations B-n using prefix reversals as generators, has similar properties. Indeed, BPn is n-regular and vertex-transitive. In this paper, we show that BPn has every cycle of length l with 8 <= l <= 2(n)n!. The proof given is a constructive one that utilizes the recursive structure of BPn. We also present a complete characterization of all the 8-cycles in BPn for n >= 2, which are the smallest cycles embeddable in BPn, by presenting their canonical forms as products of the prefix reversal generators. (C) 2019 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据