论文标题
在煎饼图的直径上
On The Diameter of Pancake Graphs
论文作者
论文摘要
煎饼图（$ p_n $）代表n个元素上所有排列的组，即$ s_n $，相对于包含所有前缀逆转的生成集。图的直径是图上所有距离的最大值，其中两个顶点之间的距离是它们之间的最短路径。对于$ p_n $，它是$ s_n $中每个排列的最短生成序列的最大生成序列。在这里，我们提出了一种方法，以实现$ p_n $直径更好的上限，该范围侧重于图形理论概念而不是代数。
The Pancake graph($P_n$) represents the group of all permutations on n elements, namely $S_n$, with respect to the generating set containing all prefix reversals. The diameter of a graph is the maximum of all distances on the graph, where the distance between two vertices is the shortest path between them. In the case of the $P_n$, it is the maximum of the shortest generating sequence of each permutation in $S_n$. Here we propose a method to realise better upper bounds to the diameter of $P_n$ that has its focus on Graph Theoretical concepts rather than Algebra.
