论文标题
广义煎饼图中的循环长度
Lengths of Cycles in Generalized Pancake Graphs
论文作者
论文摘要
在本文中，我们考虑可以嵌入广义煎饼图的边缘的循环的长度，这些煎饼图是由前缀逆转产生的广义对称组$ s（m，n）$的cayley图。广义的对称组$ s（m，n）$是订单$ m $的环形组和对称订单$ n！$的对称组的产品。我们的主要重点是基础\ emph {无方向}图，由$ \ mathbb {p} _m（n）$表示。在循环基团具有一个或两个元素的情况下，这些图分别与煎饼图和燃烧的煎饼图是同构。我们证明，当循环组具有三个元素时，$ \ mathbb {p} _3（n）$具有所有可能长度的循环，因此类似于薄煎饼图和燃烧的煎饼图的类似属性。此外，$ \ mathbb {p} _4（n）$具有所有均匀的周期。我们将这些结果用作基本案例，并表明，如果$ m> 2 $偶数，则$ \ mathbb {p} _m（n）$具有从腰围到哈米尔顿循环的所有均匀长度。此外，当$ m> 2 $是奇数时，$ \ mathbb {p} _m（n）$具有从腰围到汉密尔顿周期的各个长度的周期。我们此外表明，$ \ mathbb {p} _m（n）$ is $ \ min \ {m，6 \} $如果$ \ min \ {m，6 \} $如果$ m \ geq3 $，则补充已知结果$ m = 1,2。$，
In this paper, we consider the lengths of cycles that can be embedded on the edges of the generalized pancake graphs which are the Cayley graph of the generalized symmetric group $S(m,n)$, generated by prefix reversals. The generalized symmetric group $S(m,n)$ is the wreath product of the cyclic group of order $m$ and the symmetric group of order $n!$. Our main focus is the underlying \emph{undirected} graphs, denoted by $\mathbb{P}_m(n)$. In the cases when the cyclic group has one or two elements, these graphs are isomorphic to the pancake graphs and burnt pancake graphs, respectively. We prove that when the cyclic group has three elements, $\mathbb{P}_3(n)$ has cycles of all possible lengths, thus resembling a similar property of pancake graphs and burnt pancake graphs. Moreover, $\mathbb{P}_4(n)$ has all the even-length cycles. We utilize these results as base cases and show that if $m>2$ is even, $\mathbb{P}_m(n)$ has all cycles of even length starting from its girth to a Hamiltonian cycle. Moreover, when $m>2$ is odd, $\mathbb{P}_m(n)$ has cycles of all lengths starting from its girth to a Hamiltonian cycle. We furthermore show that the girth of $\mathbb{P}_m(n)$ is $\min\{m,6\}$ if $m\geq3$, thus complementing the known results for $m=1,2.$
