一类4度无平方因子阶边传递图的分类

Classification of Tetravalent Edge-Transitive Graphs of Square-Free Order

摘要: 设$\Gamma$ 是一个无平方因子阶的4度连通图，且$G\le Aut\Gamma$ 是几乎单群，$G$ 在顶点集上作用是本原的且在边集上是传递的，若图是非2-弧传递的，则存在唯一性。本文研究了此类图的结构与分类问题，通过引入陪集图构造，结合本原置换群理论及已知的有限单群分类结果，我们完整刻画了所有满足条件的图。本文的结果推广了无平方因子阶对称图的相关研究，并为更高度数图的分类提供了参考。

Abstract: Let $\Gamma$ be a finite connected tetravalent graph of square-free order, and let $G\le Aut\Gamma$ be an almost simple group acting primitively on the vertex set and transitively on the edge set. If the graph is not $\left(G,2\right)$ -arc-transitive, then it is unique. This paper investigates the structure and classification of such graphs. By introducing coset graph constructions and combining the theory of primitive permutation groups with known classifications of finite simple groups, we completely characterize all graphs satisfying these conditions. The results of this paper generalize related studies on symmetric graphs of square-free order and provide a reference for the classification of graphs of higher valency.

1. 引言

本文所研究的图均为有限、无向、无重边的简单图。

设$\Gamma =\left(V,E\right)$ 是一个4度图，其中$V$ 表示顶点集，$E$ 表示边集，顶点数$\left|V\right|$ 称为$\Gamma$ 的阶数。令$Aut\left(\Gamma \right)$ 为$\Gamma$ 的自同构群，并设$G$ 是$Aut\left(\Gamma \right)$ 的一个子群，记作$G\le Aut\left(\Gamma \right)$ 。若$G$ 分别在顶点集、边集上传递，则称图$\Gamma$ 是$G$ -点传递、$G$ -边传递的。每条边$\left\{\alpha ,\beta \right\}\in E$ 对应两个有序数对$\left(\alpha ,\beta \right)$ 和$\left(\beta ,\alpha \right)$ 称为$\Gamma$ 的弧，若$G$ 在弧集上传递，则称$\Gamma$ 是$G$ -弧传递的。

在图论研究中，对称图的结构与分类始终是核心研究方向之一。我们对奇数阶2倍素数度弧传递的研究早在1993年，徐明耀教授完成了一类重要图的分类，是度数为两个不同奇素数乘积的点本原图[1]，为后续对称图、点传递非凯莱图的分类奠定了重要基础。进入21世纪，李才恒教授在[2]中取得重要进展，证明了如果奇数阶对称图最多为3-弧传递图，这类图均可由几乎单群构成。随后，在2021年和2023年，李才恒教授等人在[3] [4]中，进一步推进了奇数阶2-弧传递图的分类，特别是在交错群与对称群情形下给出完整刻画。这些研究不仅推动了对称图研究的深入发展，也为本原图的研究提供了新视角。近年来，冯涛教授等人完成了有限几乎单群的可解因子的完全分类[5]，即对任意几乎单群$G$ ，明确刻画了所有满足$G=HK$ 的可解子群$H$ (其中$K$ 为$G$ 的无核子群)。该工作不仅完善了几乎单群因子分解的内容，还被进一步应用于拟本原置换群的分类，并给出了具有可解传递子群的拟本原群的结构定理。同年，李靖建教授在[6]论文中，对度数为两个不同素数幂乘积的基本2-弧传递图给出了完全分类，推进了Praeger提出的经典问题。

关于无平方因子阶对称图的研究，其背景可追溯至对特殊度数对称图的早期探索。冯涛教授于2010年完成了5度正则图的完全分类，构造二面体群上的Cayley图，开启了对具体度数无平方因子阶图的研究[7]。随后，2015年李才恒教授研究了无平方因子阶边传递图[8]，并在此基础上确定了无平方因子阶局部本原图弧传递图的自同构群。紧接着在2016年又进一步，系统研究了无平方因子阶的弧传递图，成功实现了对5、6、7度局部本原弧–传递图的完全分类[9]。在2019年路在平教授等人成功将分类推广至11度弧传递图[10]，并给出了包括完全二分图、二面体群Cayley图以及与$J_1$ 和$PSL\left(2,p\right)$ 相关图例在内的完整列表。这些研究清晰地展示了从理论到具体度数分类，不断扩展的学术发展路径。

本文将研究了4度无平方因子阶，点传递、边传递图。通过构造陪集和本原置换群，证明此类图在非2-弧传递且本原、几乎单的条件下是唯一存在的。

定理1.1 设$\Gamma =\left(V,E\right)$ 是一个无平方因子阶的4度连通图，且$G\le Aut\Gamma$ 是一个几乎单群，在顶点集$V$ 上作用是本原的，边集$E$ 上是传递的。则下述结论之一成立：

(1) $G=S_7$ ，$\left|V\right|=35$ ，此时$\Gamma$ 同构于Odd图$O_4$ ；

(2) $G=PSL\left(2,p\right)$ ，其中$p\ne 7$ 且$p\equiv \pm 1\left(\mathrm{mod}8\right)$ ，且$\left|V\right|=\frac{p\left(p^2-1\right)}{48}$ ；

(3) $G=PSL\left(2,p\right)$ ，其中$p\ne 5$ 且$p\equiv \pm 3\left(\mathrm{mod}8\right)$ ，且$p\ne 1\left(\mathrm{mod}10\right)$ ，且$\left|V\right|=\frac{p\left(p^2-1\right)}{24}$ ；

(4) $G=PGL\left(2,p\right)$ ，其中$p\equiv \pm 3\left(\mathrm{mod}8\right)$ ，且$\left|V\right|=\frac{p\left(p^2-1\right)}{24}$ ；

(5) $G=PGL\left(2,7\right)$ ，$\left|V\right|=21$ ，此时$\Gamma$ 是与例3.1中的图同构。

2. 预备知识

本节将介绍一些重要的定义，引理和定理，为后续的内容奠定基础。

首先，我们引入陪集图的概念。设$G$ 是一个抽象群，其子群$H\le G$ 称为无核的，即$H$ 中不包含$G$ 中任何非平凡的正规子群。对于子集$S\subseteq G$ ，可定义一个有向图陪集图$\Gamma =\mathrm{Cos}\left(G,H,HSH\right)$ ，其顶点集为$V\Gamma =\left[G:H\right]=\left\{Hx|x\in G\right\}$ ，边集为$E\left(\Gamma \right)=\left\{\left\{Hx,Hy\right\}|y{x}^{-1}\in HSH\right\}$ 。由此容易推得，任意元素$g\in G$ 通过陪集作用诱导出图$\Gamma$ 的一个自同构，即：$g:Hx\mapsto Hxg$ ，对于任意$x\in G$ 在陪集作用下，$G$ 在顶点集$V\Gamma$ 上的作用是忠实的，因此我们可以将$G$ 视为$Aut\Gamma$ ($\Gamma$ 的全自同构群)的一个子群，即$G\le Aut\Gamma$ 。于是，$G$ 在$V\Gamma$ 上的作用是传递的，且$\Gamma$ 是$G$ -顶点传递的。如果$H{S}^{-1}H=HSH$ 成立，则$\Gamma$ 的邻接关系是对称的，因此通过将两条弧(有向边) ($Hx$ , $Hy$ )和($Hy$ , $Hx$ )等同于一条无向边$\left\{Hx,Hy\right\}$ ，$\Gamma$ 可被视为一个无向图。

其次是有关陪集图的两个重要引理：

引理2.1. [11]设$\Gamma =\cos \left(G,H,HSH\right)$ 是一个无向陪集图，那么

(1) $\Gamma$ 是连通的当且仅当$\langle H,S\rangle =G$ ；

(2) $\Gamma$ 是$G$ -边传递的当且仅当存在某个$g\in G$ ，使得$HSH=H\left\{g,g^{-1}\right\}H$ ；

(3) $\Gamma$ 是$G$ -弧传递的当且仅当存在某个$g\in G$ 满足$g^2\in H$ 且$HSH=HgH$ 。

当图具有边传递性时，该度数可以进一步写成如下形式：

引理2.2. [12]设$\Gamma =\mathrm{Cos}\left(G,H,HSH\right)$ 是无向陪集图，$\Gamma$ 是$G$ -边传递的存在某个$g\in G$ ，且$HSH=HgH$ ，则$\Gamma$ 的度数等于$\left|H:H\cap H^g\right|$ ；若$\Gamma$ 是$G$ -弧传递的，则度数仍为$\left|H:H\cap H^g\right|$ ；若$\Gamma$ 是$G$ -边传递但非弧传递，则度数为$2\left|H:H\cap H^g\right|$ 。

紧接着，我们引入$s$ -弧传递的相关定义。设$\Gamma =\left(V,E\right)$ 是一个图，$s$ 为正整数。$\Gamma$ 中的一条$s$ -弧是由$s+1$ 个顶点组成的序列${\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_s$ ，使得${\alpha }_i$ 与${\alpha }_{i+1}$ 相邻且${\alpha }_i\ne {\alpha }_{i+2}$ 。设$G\le Aut\Gamma$ ，若$G$ 在$V$ 上传递作用，并且在$\Gamma$ 的$s$ -弧上传递，则称图$\Gamma$ 是$\left(G,s\right)$ -弧传递的。若进一步$G$ 在$\left(s+1\right)$ -弧上非传递，则称$\Gamma$ 是$\left(G,s\right)$ -传递的。

关于度数为4的$s$ -弧传递图，其点稳定化子已有完整分类。

引理2.3 [13]设$\Gamma =\left(V,E\right)$ 是一个连通的$\left(G,s\right)$ -传递图，度数为4，其中$s\ge 2$ 。则对于$\alpha \in V$ ，稳定子$G_{\alpha }$ 以及$s$ 的取值如下表1：

Table 1. Classification of vertex-stabilizers

表1. 点稳定子的分类

$s$	2	3	4	7
$G_{\alpha }$	$A_4,S_4$	$Z_3\times A_4,\left(Z_3\times A_4\right).Z_2,S_3\times S_4$	$Z_3^2:GL\left(2，3\right)$	$\left[3^5\right]:GL\left(2,3\right)$

最后，我们给出点本原4度弧传递图分类结果来结束本节。

定理2.4 [14]设$\Gamma$ 是一个度数为$l=4$ 的点本原弧传递图，能得到以下结论。其中，$p$ 为素数，$n$ 为$\Gamma$ 的顶点数，$\Gamma$ 是$m$ 个互不同构的$s$ -传递图之一，其$s$ 、$m$ 、$n$ 以及$Aut\left(\Gamma \right)$ 如表2所示。

此外，$\Gamma$ 是群$R$ 的Cayley图当且仅当$Aut\left(\Gamma \right)=Z_p:Z_4$ ，$Z_p^2:D_8$ ，$PGL\left(2,5\right)$ ，$PGL\left(2,7\right)$ ，$PGL\left(2,11\right)$ 或$PSL\left(2,23\right)$ ，且相应的$R$ 分别为$Z_p$ ，$Z_p^2$ ，$Z_5$ ，$Z_7:Z_3$ ，$Z_{11}:Z_5$ ，$Z_{23}:Z_{11}$ 。

Table 2. Classification of 4-valent vertex-primitive arc-transitive graphs

表2. 4度点本原弧传递图的分类

$Aut\Gamma$	Vertex-stabiliser	$s$	$n$	$m$	Comments
$Z_p:Z_4$	$Z_4$	1	$p$	1	$p>5$
$Z_p^2:D_8$	$D_8$	1	$p^2$	1	$p\ge 3$
$PSL\left(2,p\right)$	$S_4$	2	$\left(p\left(p^2-1\right)\right)/48$	1	$p\equiv \pm 1\left(\mathrm{mod}8\right),p\ne 7$
$PSL\left(2,p\right)$	$A_4$	2	$\left(p\left(p^2-1\right)\right)/24$	$\left[\left(p+\epsilon \right)/12\right]$	$\begin{array}{l}p\equiv \pm 3\left(\mathrm{mod}8\right),p\ne 5,\epsilon =\pm 1\\ 3\text{|}\left(p+\epsilon \right),p\ne \pm 1\left(\mathrm{mod}10\right)\end{array}$
$PGL\left(2,p\right)$	$S_4$	2	$\left(p\left(p^2-1\right)\right)/24$	1	$p\equiv \pm 3\left(\mathrm{mod}8\right)$
$PGL\left(2,7\right)$	$D_{16}$	1	21	1	Cayley
$Aut\left(A_6\right)$	$\left[2^5\right]$	1	45	1	non-Cayley
$PSL\left(2,17\right)$	$D_{16}$	1	153	1	non-Cayley
$S_7$	$S_4\times S_3$	3	35	1	odd graph
$PSL\left(3,7\right)$	$\left(A_4:Z_3\right):Z_2$	3	26068	1	non-Cayley

3. 定理1.1

首先在证明定理之前，我们先构造一类无平方因子阶4度图。

例3.1的构造，设$G=PGL\left(2,7\right)$ ，$N=PSL\left(2,7\right)$ 。在$G$ 中存在一个子群$H\cong D_{16}$ (16阶二面体群)，且$H$ 不包含于$N$ ，即$H\cap N\cong D_8$ 。令$K\le H\cap N$ 满足$K\cong Z_2^2$ ，则$K$ 在$H$ 中的正规化子为$N_H\left(K\right)\cong D_8$ ，而在$G$ 中的正规化子为$N_G\left(K\right)\cong S_4$ 。

特别地，$N_N\left(K\right)\cong S_4$ 且$N_H\left(K\right)\subset N_N\left(K\right)$ 。选取一个对合$x\in N_N\left(K\right)\backslash H$ (这样的$x$ 存在，因为$N_N\left(K\right)\cong S_4$ 而$N_H\left(K\right)\cong D_8$ 是$S_4$ 的一个子群)。构造陪集图$\Gamma =\mathrm{Cos}\left(G,H,HxH\right)$ ，其顶点集为$G/H$ ，边集由$\left\{Hg,Hxg\right\}$ 给出(由于$x$ 是对合，$HxH=Hx$ 为单陪集)。易证$\Gamma$ 是连通的4度图，且$G$ 在$\Gamma$ 上弧传递。$\Gamma$ 的阶为$21=3\times 7$ ，无平方因子。进一步，该图$\Gamma$ 是两个弧传递的2度图的边不交并，其中每个图由7个长度为3的圈顶点不交并构成。这就是我们需要构造的图。

接下来，我们来证明定理1.1。假设$\Gamma =\left(V,E\right)$ 是一个无平方因子阶4度连通图，$G\le Aut\Gamma$ 且$\Gamma$ 是$G$ -弧传递的，$G$ 是几乎单群且在$V$ 上本原作用。由表2可知，所有4度点本原弧传递图已经被完全列出，故我们可以逐一验证：

由于$G$ 是几乎单群，其基柱为非交换单群，故表2中第一行$Aut\left(\Gamma \right)=Z_p:Z_4$ 和第二行$Aut\left(\Gamma \right)=Z_p^2:D_8$ 对应的自同构群为仿射型，矛盾。进一步要求阶为无平方因子，其中第七行$n=45=3^2\times 5$ 、第八行$n=153=3^2\times 17$ 、第十行$n=26068$ ，都有平方因子阶，排除。因此满足条件的只有对应的第3，4，5，6，9行可能满足条件。

根据文献[13]中定理4.7，对于无平方因子阶的4度边传递图，其自同构群的基柱$soc\left(G\right)$ 只能同构于$A_7$ ，$J_1$ ，$PSL\left(3,3\right)$ ，$PSL\left(2,p\right)$ ($p\ge 5$ 素数)结合图的无平方因子阶，进一步分析：

假设$soc\left(G\right)\cong J_1$ ，则此时$G=soc\left(G\right)\cong J_1$ 于表2的分类矛盾。$J_1$ 在表2中并未出现所以可以排除这个情况。若$soc\left(G\right)\cong PSL\left(3,3\right)$ ，则由引理2.4可知，$G\cong PSL\left(3,3\right)\cdot Z_2$ 与表2中的分类矛盾。

当$soc\left(G\right)\cong A_7$ ，此时$G\cong S_7$ ，令集合$\Omega =\left\{1,2,3,4,5,6,7\right\}$ 的所有3元子集组成图$\Gamma$ 的点集，且$\left(\alpha ,\beta \right)\in E$ 当且仅当$\alpha \cap \beta =\varnothing$ 。可验证$\Gamma \cong O_4$ ，因此$O_4$ 是一个阶为35，度数为4的图，并且满足定理中的条件，此时$\Gamma$ 是$\left(G,3\right)$ -传递的。符合定理1.1中的情形(1)。

下面讨论$soc\left(G\right)\cong PSL\left(2,p\right)$ 的情况。

若$\Gamma$ 是$\left(G,2\right)$ -弧传递的，则由表1可知$G_{\alpha }\cong A_4$ 或$S_4$ 。结合$G$ 的本原性及表1的分类可知，定理1.1中的(2)~(4)部分成立。

若$\Gamma$ 不是$\left(G,2\right)$ -弧传递的，令$\alpha \in V$ ，则由$PGL\left(2,p\right)$ 的子群分类结果可知$G_{\alpha }\cong Z_2^2$ ，$Z_{2^s}$ 或$D_{2^t}$ 。其中$s=1$ ，$t\ge 3$ 再结合表2可知$G_{\alpha }\cong D_{16}$ 。此时$G=PGL\left(2,7\right)$ ，$soc\left(G\right)=PSL\left(2,7\right)$ 相应的图由例3.1给出，于是定理证得。

由定理1.1的证明可直接得出如下推论：

推论3.2设$\Gamma =\left(V,E\right)$ 是一个无平方因子阶的4度连通图，且$G\le Aut\Gamma$ 是几乎单群，在顶点集上作用本原，在边集上传递。若$\Gamma$ 不是$\left(G,2\right)$ -弧传递的，则$\Gamma$ 唯一存在，且同构于例3.1中构造的陪集图。