构造与证明：(n,k)-排列图的Cayley陪集图性质

本文主要探讨了排列图的代数性质，特别是在Cayley陪集图的构建和分析方面。作者林丽美和周书明通过对(n, k)-排列图An,k的研究，提出了一个新颖的Cayley陪集图构造方法。Cayley图是一种基于群论的概念，它将群中的元素与特定的生成子集相对应，形成图的顶点和边，从而构建出具有特定群结构的图形。 在论文中，他们首先定义并构造了一种新的Cayley陪集图，这种图通过(n, k)置换集V(An,k)上的置换操作来定义，每个置换代表图中的一个节点，而节点之间的连接则依据特定的运算规则。这种结构使得Cayley陪集图能够与(n, k)-排列图An,k建立起直接的关系，即An,k实际上可以被视为基于对称群的Cayley陪集图。 接着，他们展示了这种新的Cayley陪集图的性质，证明了其与已知的(n, k)-排列图An,k在代数上是等价的，即存在同构映射使得两个图在结构上保持一致。这一发现对于理解排列图的内在结构以及它们在图论中的地位至关重要，因为它揭示了排列图的对称性和传递性。 (n, k)-排列图An,k的点传递性是指对于图中的任意两个顶点，存在路径可以通过一系列相邻的顶点直接相连，无需经过其他顶点。这对于许多图论应用（如网络设计、数据压缩和密码学）来说是非常有用的属性，因为它确保了信息传输的高效性和安全性。 这篇论文不仅深化了对Cayley陪集图和排列图之间关系的理解，而且为这些图形在代数结构和实际应用中的研究提供了新的视角。通过证明排列图An,k是基于对称群的Cayley陪集图，作者们扩展了我们对图形理论中这些复杂结构的认识，为后续的理论研究和实际问题解决奠定了坚实的基础。