广义Petersen图$P_{2,7}$的边传递性

Edge Transitivity of the Generalized Petersen Graph $P_{2,7}$

摘要: 广义Petersen图$P_{k,n}$ 是一种在图论中具有重要研究价值的正则图，其独特的对称性与复杂的结构特性使其在图论中具有广泛的应用价值。文章以广义Petersen图中的$P_{2,7}$ 为研究对象，通过深入分析其顶点构造与自同构群的特性，结合严格的理论推导，详细证明了$P_{2,7}$ 并非边传递图。

Abstract: The generalized Petersen graph $P_{k,n}$ is a class of regular graphs with significant research value in graph theory. Its unique symmetry and complex structural properties make it widely applicable in various areas of graph theory. This paper focuses on the generalized Petersen graph $P_{2,7}$ , conducting an in-depth analysis of its vertex construction and automorphism group. Through rigorous theoretical derivation, it is demonstrated in detail that $P_{2,7}$ is not edge-transitive, providing new theoretical insights into the study of symmetry and transitivity in generalized Petersen graphs.

1. 引言

广义Petersen图$P_{k,n}$ 是一种具有对称性和正则性的图[1]，其结构特性吸引了图论研究者的广泛兴趣。它是由Coxeter于1950年首次定义的一类特殊图[2]。其顶点数为2n，包含n个外圈顶点和n个内圈顶点，通过特定规则连接，形成一个三正则图。经典的Petersen图是广义Petersen图的一个特例。

在1971年，Frucht等人对广义Petersen图的自同构群进行了深入研究，指出其自同构群的结构与参数n和k密切相关[3]。通过分析图的边传递性与顶点传递性，讨论了若干特殊参数组合下图的对称性和群的表示形式。

广义Petersen图$P_{k,n}$ 定义可以写成如下形式：

顶点集：$V=\left\{x_1,x_2,\cdots ,x_n,y_1,y_2,\cdots ,y_n\right\}$ ，其中$x_i$ 构成外圈顶点，$y_i$ 构成内圈顶点；

边集：E包括以下三类边：

1) 外圈边：$x_i{x}_{i+1}$ ，其中下标按模n计算；

2) 内圈边：$y_i{y}_{i+k}$ ，其中下标按模n计算；

3) 辐条边：$x_i{y}_i$ 。

当$k=2$ 且$n=7$ 时，得到$P_{\text{2},7}$ ，这是一张由14个顶点和21条边组成的正则图。经典的Petersen图$P_{\text{2},5}$ 是广义Petersen图的一个特殊例子。本文旨在通过逻辑推导，证明$P_{\text{2},7}$ 不是边传递的。

2. 图的构造与自同构映射

顶点集又分为两部分：外圈顶点和内圈顶点。顶点集可记为：$V=\left\{x_1,x_2,\cdots ,x_7\}\cup \{y_1,y_2,\cdots ,y_7\right\}$ 。

边集由外圈边$E_o$ 、内圈边$E_i$ 、辐射边$E_s$ 组成。分别如下表示：

$E_o=\left\{x_1{x}_2,x_2{x}_3,\cdots ,x_7{x}_1\right\}$ ；

$E_i=\left\{y_1{y}_3,y_2{y}_4,\cdots ,y_7{y}_2\right\}$ ；

$E_s=\left\{x_1{y}_1,x_2{y}_2,\cdots ,x_7{y}_7\right\}$ 。

为了更便于区分，将其外圈顶点涂色为红色，内圈顶点涂色为蓝色，见图1。

在图论中，自同构是指图到自身的一种双射映射，同时保持图的结构特征。这意味着自同构不仅需要保持图中顶点间的邻接关系，还需要保持顶点间的非邻接关系。更具体地说，设$G=\left(V,E\right)$ 是一个图，其顶点集为V，边集为E。一个自同构是顶点集上的一个双射$\theta :V\to V$ ，满足以下条件：

1) 邻接关系保持：对于任意边$uv\in E$ ，映射后的顶点$\theta \left(u\right)$ 和$\theta \left(v\right)$ 是邻接的，即$\theta \left(u\right)\theta \left(v\right)\in E$ ;

2) 非邻接关系保持：对于任意边$u^{\prime }{v}^{\prime }\notin E$ ，映射后的顶点$\theta \left(u^{\prime }\right)$ 和$\theta \left(v^{\prime }\right)$ 是非邻接的，即$\theta \left(u^{\prime }\right)\theta \left(v^{\prime }\right)\notin E$ 。

从而确保了图的整体结构在自同构下完全不变。自同构不仅反映了图的对称性特征，也是进一步分析图的结构性质和分类问题的重要基础[4]。

Figure 1. The generalized Petersen graph $P_{\text{2},7}$

图1. 广义彼得森图$P_{\text{2},7}$

在代数图论和群论研究中，自同构群的结构是理解图的对称性与传递性的关键。特别是在对称图和传递图的研究中，自同构群能够帮助描述图的对称操作及其性质。在1989年，黄平安系统研究了特定类型群的自同构群[5]，其中利用半直积与全形群的方法为解决图的对称性问题提供了理论支持。这些研究为分析复杂图形，如广义Petersen图的自同构群特性提供了重要参考。

3. 边传递性的定义与假设

图论中的对称性和稳定性研究是代数图论领域的重要研究方向，对称性包括图的顶点传递性、边传递性和对称操作的几何特征，而稳定性则关注图的结构在变化过程中的保持性。

在2019年，秦艳丽在博士论文中，对双凯莱图的边传递性进行了系统的分类研究，并结合广义Petersen图深入探讨了图的自同构群与稳定性之间的关系[6]。文中详细证明了在特殊参数下广义Petersen图的标准双重覆盖的全自同构群性质，为分析广义Petersen图的边传递性提供了理论依据。

在研究广义Petersen图的边传递性时，广泛的图论研究指出，某些特殊的广义Petersen图具有自同构群，这些图在图的结构上具有高度的对称性，特别是与边传递性和顶点传递性相关的对称性。García-Marco和Knauer通过研究广义Petersen图的端同态和自同构群，提出了边传递性和端同态传递性之间的关系，并给出了相应的字符化结果。他们的研究表明，边传递性的广义Petersen图具有特殊的代数结构，部分图(如Petersen图)可以看作是某些单体群的Cayley图，进一步揭示了这类图的代数特性与其边传递性之间的联系。[7]

图G是边传递的，当且仅当对任意两条边$e_1{e}_2\in E\left(G\right)$ ，存在一个自同构$\phi \in Aut\left(G\right)$ ，使得$\phi \left(e_1\right)=e_2$ 。为了验证$P_{\text{2},7}$ 的边传递性，我们尝试构造这样的映射，并通过分析自同构的限制条件来得出结论。所有在本文中没有明确定义的专业术语都可以在参考文献[8]中找到。

在研究图的边传递性和度量维度时，广义Petersen图作为一个具有重要对称性的图类，已被广泛应用于多个领域。Ismail等人在文献[9]中深入探讨了广义Petersen图的局部度量解耦性，并提出了计算这些图的局部度量基(LMB)和局部度量维度(LMD)的有效算法。该研究特别关注了$P\left(n,1\right)$ 、$P\left(n,2\right)$ 和$P\left(n,3\right)$ 类图的局部度量维度，并通过详细的计算展示了这些图的LMD值对不同节点数量的依赖性。这项研究的成果对广义Petersen图的边传递性分析具有重要意义，尤其是在确定图的最优设施位置等实际应用方面，提供了新的理论支持。因此，在分析广义Petersen图$P_{2,7}$ 的边传递性时，相关局部度量维度的计算和算法也可能提供有价值的视角与方法。

4. $P_{2,7}$ 的边传递性证明

证明：反证法。假定$P_{2,7}$ 是边传递的，构造所有可能的自同构，尝试构造自同构$\theta$ 满足：$\theta \left(x_1{y}_1\right)=x_4{x}_5$ ，即$x_1{y}_1\to x_4{x}_5$ 。

则有$\{\begin{array}{l}{x}_1\to x_4\\ y_1\to x_5\end{array}$ 或$\{\begin{array}{l}{x}_1\to x_5\\ y_1\to x_4\end{array}$ 。这两个式子是等价的，因此下面只讨论$\{\begin{array}{l}{x}_1\to x_4\\ y_1\to x_5\end{array}$ 这一情况，此式命名为(A)。因此有$N\left(x_1\right)\to N\left(x_4\right)$ ，即$\left\{y_1,x_2,x_7\right\}\to \left\{y_4,x_3,x_5\right\}$ 。由(A)，$y_1\to x_5$ ，则有$\{\begin{array}{l}{x}_2\to y_4\\ x_7\to x_3\end{array}$ 或$\{\begin{array}{l}{x}_2\to x_3\\ x_7\to y_4\end{array}$ 两种情况，分别命名为情形1和情形2。

情形1. $\{\begin{array}{l}{x}_2\to y_4\\ x_7\to x_3\end{array}$

则有$N\left(x_2\right)\to N\left(y_4\right)$ ，即$\left\{x_1,y_2,x_3\right\}\to \left\{x_4,y_2,y_6\right\}$ 。由(A)，$x_1\to x_4$ ，则有$\{\begin{array}{l}{x}_3\to y_6\\ y_2\to y_2\end{array}$ 或$\{\begin{array}{l}{y}_2\to y_6\\ x_3\to y_2\end{array}$ 两种情况，分别命名为情形1.1和情形1.2。

情形1.1. $\{\begin{array}{l}{x}_3\to y_6\\ y_2\to y_2\end{array}$

则有$N\left(x_3\right)\to N\left(y_6\right)$ ，即$\left\{y_3,x_2,x_4\right\}\to \left\{x_6,y_1,y_4\right\}$ 。由情形1，$x_2\to y_4$ 。下面分两种情况分别命名为情形1.1.1和情形1.1.2。

情形1.1.1. $\{\begin{array}{l}{y}_3\to y_1\\ x_4\to x_6\end{array}$

则有$N\left(y_3\right)\to N\left(y_1\right)$ ，即$\left\{x_3,y_1,y_5\right\}\to \left\{x_1,y_3,y_6\right\}$ 。由于$y_1\to x_5\notin N\left(y_1\right)$ ，得到矛盾。

情形1.1.2. $\{\begin{array}{l}{y}_3\to x_6\\ x_4\to y_1\end{array}$

则有$N\left(y_3\right)\to N\left(x_6\right)$ ，即$\left\{x_3,y_1,y_5\right\}\to \left\{y_6,x_5,x_7\right\}$ 。因为已有$y_1\to x_5$ ，且由情形1.1，$x_3\to y_6$ ，因此有$y_5\to x_7$ 。则有$N\left(y_5\right)\to N\left(x_7\right)$ ，即$\left\{x_5,y_3,y_7\right\}\to \left\{x_1,x_6,y_7\right\}$ 。由情形1.1.2，有$y_3\to x_6$ 。下面分两种情况分别命名为情形1.1.2.1和1.1.2.2。

情形1.1.2.1. $\{\begin{array}{l}{y}_7\to x_1\\ x_5\to y_7\end{array}$

则有$N\left(y_7\right)\to N\left(x_1\right)$ ，即$\left\{x_7,y_2,y_5\right\}\to \left\{y_1,x_2,x_7\right\}$ 。由于$x_7\to x_3\notin N\left(x_1\right)$ ，得到矛盾。

情形1.1.2.2. $\{\begin{array}{l}{y}_7\to y_7\\ x_5\to x_1\end{array}$

则有$N\left(x_5\right)\to N\left(x_1\right)$ ，即$\left\{y_5,x_4,x_6\right\}\to \left\{x_2,y_1,x_7\right\}$ 。由1.1.2，$x_4\to y_1$ ，$y_5\to x_7$ ，因此$x_6\to x_2$ 。则有$N\left(x_6\right)\to N\left(x_2\right)$ ，即$\left\{y_6,x_5,x_7\right\}\to \left\{x_1,x_3,y_2\right\}$ 。由情形1.1.2.2和情形1，分别有$x_5\to x_1$ 和$x_7\to x_3$ ，因此$y_6\to y_2$ 。则有$N\left(y_6\right)\to N\left(y_2\right)$ ，即$\left\{y_1,y_4,x_6\right\}\to \left\{x_2,x_4,y_7\right\}$ 。由于$y_1\to x_5\notin N\left(y_2\right)$ ，得到矛盾。

情形1.2. $\{\begin{array}{l}{y}_2\to y_6\\ x_3\to y_2\end{array}$

则有$N\left(y_2\right)\to N\left(y_6\right)$ ，即$\left\{x_2,y_4,y_7\right\}\to \left\{y_1,y_4,x_6\right\}$ 。由情形1，$x_2\to y_4$ 。下面分两种情况分别命名为情形1.2.1和情形1.2.2。

情形1.2.1. $\{\begin{array}{l}{y}_7\to x_6\\ y_4\to y_1\end{array}$

则有$N\left(y_7\right)\to N\left(x_6\right)$ ，即$\left\{x_7,y_2,y_5\right\}\to \left\{x_5,x_7,y_6\right\}$ 。由于$x_7\to x_3\notin N\left(x_6\right)$ ，得出矛盾。

情形1.2.2. $\{\begin{array}{l}{y}_7\to y_1\\ y_4\to x_6\end{array}$

则有$N\left(y_7\right)\to N\left(y_1\right)$ ，即$\left\{y_2,y_5,x_7\right\}\to \left\{x_1,y_3,y_6\right\}$ 。由于$x_7\to x_3\notin N\left(y_1\right)$ ，得出矛盾。

情形2. $\{\begin{array}{l}{x}_2\to x_3\\ x_7\to y_4\end{array}$

则有$N\left(x_2\right)\to N\left(x_3\right)$ ，即$\left\{x_1,x_3,y_2\right\}\to \left\{x_2,x_4,y_3\right\}$ 。由(A)，$x_1\to x_4$ 。下面分为两种情况，分别命名为情形2.1和情形2.2。

情形2.1. $\{\begin{array}{l}{y}_2\to x_2\\ x_3\to y_3\end{array}$

则有$N\left(y_2\right)\to N\left(x_2\right)$ ，即$\left\{x_2,y_4,y_7\right\}\to \left\{x_1,x_3,y_2\right\}$ 。由情形2，$x_2\to x_3$ 。下面分两种情况分别命名为情形2.2.1和情形2.2.2。

情形2.1.1. $\{\begin{array}{l}{y}_7\to x_1\\ y_4\to y_2\end{array}$

则有$N\left(y_7\right)\to N\left(x_1\right)$ ，即$\left\{x_7,y_2,y_5\right\}\to \left\{x_2,y_1,y_7\right\}$ 。由于$x_7\to y_4\notin N\left(x_1\right)$ ，得到矛盾。

情形2.1.2. $\{\begin{array}{l}{y}_7\to y_2\\ y_4\to x_1\end{array}$ 则有$N\left(y_7\right)\to N\left(y_2\right)$ ，即$\left\{y_2,y_5,x_7\right\}\to \left\{x_2,y_4,y_7\right\}$ 。由情形2.1和情形2，分别有$y_2\to x_2$ 和$x_7\to y_4$ 。因此，$y_5\to y_7$ 。下面分为两种情况，分别命名为情形2.1.2.1和情形2.1.2.2。

情形2.1.2.1. $\{\begin{array}{l}{x}_5\to x_7\\ y_3\to y_5\end{array}$

则有$N\left(x_5\right)\to N\left(x_7\right)$ ，即$\left\{y_5,x_4,x_6\right\}\to \left\{x_1,x_6,y_7\right\}$ 。由情形2.1.2，$y_5\to y_7$ 。下面分为两种情况。

情形2.1.2.1.1. $\{\begin{array}{l}{x}_4\to x_1\\ x_6\to x_6\end{array}$

则有$N\left(x_4\right)\to N\left(x_1\right)$ ，即$\left\{x_3,x_5,y_4\right\}\to \left\{x_2,x_7,y_1\right\}$ 。由于$y_4\to x_1\notin N\left(x_1\right)$ ，得出矛盾。

情形2.1.2.1.2. $\{\begin{array}{l}{x}_4\to x_6\\ x_6\to x_1\end{array}$

则有$N\left(x_4\right)\to N\left(x_6\right)$ ，即$\left\{x_3,x_5,y_4\right\}\to \left\{x_5,x_7,y_6\right\}$ 。由情形2.1.2.1，可得$x_5\to x_7$ 。由于$y_4\to x_1\notin N\left(x_6\right)$ ，得出矛盾。

情形2.1.2.2. $\{\begin{array}{l}{x}_5\to y_5\\ y_3\to x_7\end{array}$

则有$N\left(x_5\right)\to N\left(y_5\right)$ ，即$\left\{y_5,x_4,x_6\right\}\to \left\{x_5,y_3,y_7\right\}$ 。由于${\theta }^{-1}\left(y_3\right)=x_3\notin N\left(x_5\right)$ ，得出矛盾。

情形2.2. $\{\begin{array}{l}{y}_2\to y_3\\ x_3\to x_2\end{array}$

则有$N\left(y_2\right)\to N\left(y_3\right)$ ，即$\left\{x_2,y_4,y_7\right\}\to \left\{x_3,y_5,y_1\right\}$ 。由情形2，$x_2\to x_3$ 。分为以下两种情况，分别命名为情形2.2.1和情形2.2.2。

情形2.2.1. $\{\begin{array}{l}{y}_7\to y_1\\ y_4\to y_5\end{array}$

则有$N\left(y_7\right)\to N\left(y_1\right)$ ，即$\left\{x_7,y_2,y_5\right\}\to \left\{x_1,y_3,y_6\right\}$ 。由情形2.2，可得$y_2\to y_3$ 。由于$x_7\to y_4\notin N\left(y_1\right)$ ，得出矛盾。

情形2.2.2. $\{\begin{array}{l}{y}_7\to y_5\\ y_4\to y_1\end{array}$

则有$N\left(y_7\right)\to N\left(y_5\right)$ ，即$\left\{x_7,y_2,y_5\right\}\to \left\{y_3,y_7,x_5\right\}$ 。由情形2.2，可得$y_2\to y_3$ 。由于$x_7\to y_4\notin N\left(y_5\right)$ ，得出矛盾。

5. 结语

通过对分类讨论，综上所述，不能构造出$x_1{y}_1$ 与$x_4{x}_5$ 之间的自同构，也就是$P_{2,7}$ 中的边在自同构下无法相互映射，所以$P_{2,7}$ 不是边传递的。