14pq阶的五度对称图

Pentavalent Symmetric Graphs of Order 14pq

摘要: 称一个图为对称图，如果它的自同构群在这个图的弧集上是传递的。丁素云、凌波、娄本功和潘江敏教授2016年在文献(Graphs and Combinatorics, 32, 2355-2366, 2016)中证明了：无平方因子阶的五度对称图要么同构于图CD_n,k、C₃₉₀ 、C₂₉₂₆，要么这类图的全自同构群为PSL(2,p)和PGL(2,p)。本文的主要工作是在假定一个五度图的阶为14pq时，完全确定其图全自同构群为PSL(2,p)和PGL(2,p)对应的对称图，其中q>p>5为素数。

Abstract: A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In 2016, Ding Suyun, Ling Bo, Lou Bengong and professors Pan Jiangmin published a paper in the (Graphs and Combinatorics, 32, 2355-2366, 2016), proved that: Arc-transitive pentavalent graphs of square-free order are either isomorphic to graphs CD_n,k、C₃₉₀ 、C₂₉₂₆ , or the full automorphism group of such graphs is PSL(2,p) and PGL(2,p) . The main work of this paper is to completely determine that the full automorphism group of a pentavalent graph as PSL(2,p) and PGL(2,p) corresponds to a symmetric graph when the order of the graph is assumed to be 14pq, where q>p>5 are primes.

1. 引言

本文所考虑的图均为有限简单无向图。给定图Γ，分别用 $V\left(\Gamma \right)$ ， $E\left(\Gamma \right)$ 和 $A\left(\Gamma \right)$ 表示图Γ的顶点集，边集和自同构群。设s是一个正整数，称Γ中 $s+1$ 个顶点序列 $V_0{V}_1\cdots V_S$ 为一个s-弧，如果 $\left(V_i,V_{i+1}\right)\in E\left(\Gamma \right)$ ， $0\le i\le s-1$ ，并且对 $s\ge 2$ ，有 $V_i\ne V_{i+2}$ ， $0\le i\le s-2$ 。称Γ为s-弧传递图，如果 $\text{Aut}\left(\Gamma \right)$ 在Γ的所有s-弧上是传递的。称Γ为s-传递图，如果Γ是s-弧传递的，但不是 $\left(s+1\right)$ -弧传递的。特别地，1-弧是一个弧，0-弧是一个顶点。令 $G\le S_{\Omega }$ ，对任意的 $\alpha \in \Omega$ ，恒有 $G_{\alpha }=1$ ，则称G是半正则的。如果群G既是半正则的又是传递的则称G是正则的。如果 $\text{Aut}\left(\Gamma \right)$ 在Γ上是正则的，则Γ被称为1-弧正则的。A在Γ的弧集上的作用是传递的当且仅当A在Γ的点集上 $V\left(\Gamma \right)$ 上是传递的，并且任一点 $v\in V\left(\Gamma \right)$ 在A中的稳定子群 ${\text{A}}_v$ 在v的邻域 ${\Gamma }_1\left(v\right)$ 上也是传递的。

研究群与图里面的对称性，也就是图的自同构群作用在图的顶点集，边集，弧集等上面的传递性，而图的弧传递图的分类一直是一个比较热门的话题。近年来，给定阶的对称图的分类得到了广泛的关注。Chao在文献 [1] 中分类了p阶的对称图，Conder [2] 等分类了所有阶小于或等于768个点的3度对称图。冯等 [3] 分类阶为8p，8p²的三度对称图。对于四度对称图的阶的分类的一些结果可以参考 [4] [5] 。而对于五度对称图的分类有许多显著的结果，只有一个素因子阶的五度对称图的分类可以参考文献 [6] [7] [8] [9] ，一个素因子阶的五度对称图大多数被分类完全，接下来对于两个素因子阶的五度对称图的分类可以参考文献 [10] [11] 。本文的主要目的是对14pq阶的五度对称图进行分类，主要采用的方法是取正规商图。

本文的主要结果是下面的定理。

定理1.1 设Γ是一个阶为14pq的连通五度对称图，其中 $p>q>5$ 是素数，所以下列表述之一成立。

(1) $\Gamma \cong {\text{CD}}_{14pq,k}$ ，其中 $5|p-1$ 和 $q-1$ 。

(2) 当 $p=139,q=23$ 时，在同构意义下，存在图 $\Gamma \cong C_{44758}$ ，进一步地， $\text{Aut}\left(\Gamma \right)=\text{PGL}\left(2,139\right)$ ， ${\text{A}}_{\alpha }={\text{A}}_5$ ，其中 $\alpha \in V\left(\Gamma \right)$ 。

2. 预备知识

在这一节中我们将引用一些基本的结果，方便后面的讨论。

以下定理在文献( [12] ，定理1.2)中得到证明。

定理2.1 令Γ是一个阶为n的连通弧传递五度图，其中n是一个无平方因子阶的整数，且至少有四个素因子。下列之一成立。

(1) $\Gamma \cong {\text{CD}}_{n,k},n=2\cdot 5^t{p}_1{p}_2\cdots p_s$ 和 $\text{Aut}\left(\Gamma \right)\cong D_n:Z_5$ ，其中 $0\le t\le 1,s\ge 2$ ， $p_1{p}_2\cdots p_s$ 是不同的素数，当 $i=1,2,\cdots ,s$ 时， $5|p_i-1$ ，在同构的情况下恰好有 $4^{s-1}$ 个这样的n阶图。

(2) $\text{Aut}\left(\Gamma \right)\cong \text{PSL}\left(2,p\right)$ 或 $\text{PGL}\left(2,p\right)$ ， $p\ge 29$ 为一个素数。

(3) 三元组 $\left(\Gamma ,n,\text{Aut}\left(\Gamma \right)\right)$ 见表1。

Table 1. Pentavalent symmetric graphs of square-free order

表1. 无平方因子阶的五度对称图

$\text{PSL}\left(2,q\right)$ 的极大子群是已知的，参见文献( [13] ，第239章节)。

引理2.2 设 $T\cong \text{PSL}\left(2,q\right)$ ，其中 $q=p^n\ge 5$ ，p是素数。那么T的极大子群同构于下列群之一，其中 $d=\left(2,q-1\right)$ 。

(1) $D_{2\left(p-1\right)/d}$ ，其中 $q\ne 5,7,9,11$ ；

(2) $D_{2\left(p-1\right)/d}$ ，其中 $q\ne 7,9$ ；

(3) $Z_q:Z_{\left(q-1\right)/d}$ ；

(4) ${\text{A}}_4$ ，其中 $q=p=5$ 或者 $q=p\equiv 3,13,27,37\left(\mathrm{mod}40\right)$ ；

(5) $S_4$ ，其中 $q=p\equiv \pm 1\left(\mathrm{mod}8\right)$ ；

(6) ${\text{A}}_5$ ，其中 $q=p\equiv \pm 1\left(\mathrm{mod}5\right)$ ，或者 $q=p^2\equiv -1\left(\mathrm{mod}5\right)$ ，p为一个奇素数；

(7) $\text{PSL}\left(2,p^m\right)$ ，n/m为一个奇整数；

(8) $\text{PGL}\left(2,P^{n/2}\right)$ ，n为偶整数。

根据文献 [14] [15] 得到五度弧传递图的点稳定子的结构。

引理2.4 设Γ是一个连通的五度 $\left(G,s\right)$ -传递图，其中 $G\le \text{Aut}\left(\Gamma \right)$ ， $s\ge 1$ ，设 $\alpha \in V\left(\Gamma \right)$ ，则下列表述之一成立：

(1) 如果 $G_{\alpha }$ 是可解的，则 $\left|G_{\alpha }\right||80$ ，且 $s\le 3$ 。此外， $\left(G_{\alpha },s\right)$ 如表2所示。

Table 2. Soluble vertex-stabilizers

表2. 可解的点稳定子

(2) 如果 $G_{\alpha }$ 是不可解的，则 $\left|G_{\alpha }\right||2^9\cdot 3^2\cdot 5$ 且 $2\le s\le 5$ 。此外， $\left(G_{\alpha },s\right)$ 如表3所示。

Table 3. Insoluble vertex-stabilizers

表3. 非可解的点稳定子

研究顶点传递图的一种典型方法是取正规商图。设Γ是一个G-顶点传递图，其中 $G\le \text{Aut}\left(\Gamma \right)$ ，令 $N⊲G$ ，且N在 $V\left(\Gamma \right)$ 上是不传递的。称商图 ${\Gamma }_N$ 是G-正规的，如果 $V\left({\Gamma }_N\right)$ 是G的某个正规子群N的轨道的集合。由N诱导的正规商图 ${\Gamma }_N$ 定义为顶点集 $V\left({\Gamma }_N\right)$ 的图。在商图 ${\Gamma }_N$ 中 $\left(B_1,B_2\right)\in E\left({\Gamma }_N\right)$ 当且仅当 $x\in B_1$ 和 $y\in B_2$ ，使得 $\left(x,y\right)\in E\left(\Gamma \right)$ 。如果原图的度数 $\text{Val}\left(\Gamma \right)$ 与块图的度数 $\text{Val}\left({\Gamma }_N\right)$ 相等，那么Γ被叫做 ${\Gamma }_N$ 的正规覆盖(参见文献( [16] 引理2.5)和( [17] ，定理4.1)。

定理2.5 设Γ是奇数度的G-弧传递图，令 $N⊲G$ 在 $V\left(\Gamma \right)$ 上至少有三个轨道。那么下列的陈述成立。

(1) N是 $V\left(\Gamma \right)$ 上的半正则， $G/N\le \text{Aut}\left({\Gamma }_N\right)$ ，Γ是的正规覆盖。

(2) $G_{\alpha }\cong {\left(G/N\right)}_{\delta }$ ，其中 $\alpha \in V\left(\Gamma \right)$ ， $\delta \in V\left({\Gamma }_N\right)$ 。

(3) Γ是 $\left(G,s\right)$ -传递的当且仅当 ${\Gamma }_N$ 是 $\left(G/N,s\right)$ -传递。

3. 定理1.1的证明

不设Γ是阶为14pq的连通五度对称图，其中 $5<q<p$ 是素数。令 $\text{A}=\text{Aut}\left(\Gamma \right)$ ， $\alpha \in V\left(\Gamma \right)$ 。

如果A是可解的，根据定理2.1， $\Gamma \cong {\text{CD}}_{14pq,k}$ 且 $5|p-1$ 和 $5|q-1$ ，定理1.1第一部分成立，假设A是不可解的，定理2.1表明，A是几乎单的 $T:=\text{soc}\left(\text{A}\right)\cong \text{PSL}\left(2,r\right)$ ，其中 $r\ge 29$ 是素数。因为 $\left|\text{PSL}\left(2,r\right)\right|$ 不整除 $\left|V\left(\Gamma \right)\right|=14pq$ ，根据定理2.5(1)，T在 $V\left(\text{Γ}\right)$ 上最多有两个轨道， $\left|T:T_{\alpha }\right|=7pq$ 或14pq。因为 $T\le \text{A}\le \text{PGL}\left(2,r\right)$ ，我们有 $\left|{\text{A}}_{\alpha }:T_{\alpha }\right|\le 2$ ，所以 $5|T_{\alpha }$ ，由于 $\left|T\right|=\left|T_{\alpha }\right|n$ ，于是 $35pq|\left|T\right|=\left|\text{PSL}\left(2,r\right)\right|$ 。此外，根据引理2.4， $\left|{\text{A}}_{\alpha }\right||2^9\cdot 3^2\cdot 5$ ，所以 $\left|T\right||2^{10}\cdot 3^3\cdot 5pq$ 。因此 $r=p$ 。

我们现在确定了p的所有可能。如果 $3|\left|{\text{A}}_{\alpha }\right|$ ，根据引理2.4， ${\text{A}}_{\alpha }$ 是不可解的，所以当 $A_{\alpha }\le T_{\alpha }.Z_2$ ，因为 $T_{\alpha }\le \text{PSL}\left(2,p\right)$ ，根据引理2.2我们进一步有 $T_{\alpha }\cong {\text{A}}_5$ 。如果3不整除 $\left|{\text{A}}_{\alpha }\right|$ ，根据引理2.4， ${\text{A}}_{\alpha }$ 是可解的，则 $\left|T_{\alpha }\right||80$ 。因此 $\left|T\right||840pq$ 或1120pq。 $\left|T\right|=p\left(p-1\right)\left(p+1\right)/2$ 且 $\left(\left(p+1\right)/2,\left(p-1\right)/2\right)=1$ 。如果q整除 $\left(p+1\right)/2$ ，则 $p-1|840$ 或1120，其中 $p\ge 29$ 并且p是一个素数。我们有 $p=31,41,43,61,71,113,281,421$ 。进一步地，我们的p还需要满足下列两个条件：

(1) $35pq\left|\right|T|=|\text{PSL}\left(2,p\right)|=$ $p\left(p-1\right)\left(p+1\right)/2$。

(2) $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right||840pq$ 或1120pq，其中 $p>q>5$ 是素数。

① 当 $p=31$ 时，由q整除 $\left(p+1\right)/2=16$ ，与 $p>q>5$ 是素数矛盾。

② 当 $p=41$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)=2^3\cdot 3\cdot 5\cdot 7\cdot 41$ ，由q需要整除 $\left(p+1\right)/2=21$ ，且 $p>q>5$ 是素数，可得 $q=7$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 7\cdot 41$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^3\cdot 3\cdot 5\cdot 7\cdot 41$ ，矛盾。

③ 当 $p=43$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)=2^2\cdot 3\cdot 7\cdot 11\cdot 43$ ，由q需要整除 $\left(p+1\right)/2=22$ ，且 $p>q>5$ 是素数，可得 $q=11$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 11\cdot 43$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 7\cdot 11\cdot 43$ ，矛盾。

④ 当 $p=61$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)=2^2\cdot 3\cdot 5\cdot 31\cdot 61$ ，由q需要整除 $\left(p+1\right)/2=31$ ，可得 $q=31$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 31\cdot 61$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 7\cdot 11\cdot 43$ ，矛盾。

⑤ 当 $p=71$ 时，由q整除 $\left(p+1\right)/2=36$ ，与 $p>q>5$ 是素数矛盾。

⑥ 当 $p=113$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)=2^4\cdot 3\cdot 7\cdot 19\cdot 113$ ，由q需要整除 $\left(p+1\right)/2=57$ ，可得 $q=19$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 19\cdot 113$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 7\cdot 11\cdot 43$ ，矛盾。

⑦ 当 $p=421$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 5\cdot 13\cdot 17\cdot 421$ 。由q需要整除 $\left(p+1\right)/2=211$ ，且 $p>q>5$ 是素数，可得 $q=13$ 或17。于是对q分情况讨论：

对于 $q=13$ ，我们把 $p,q$ 的值代入条件(1)，此时 $35\cdot 421\cdot 13$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 5\cdot 13\cdot 17\cdot 421$ ，矛盾。

对于 $q=13$ ，我们把 $p,q$ 的值代入条件(1)，此时 $35\cdot 421\cdot 17$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 5\cdot 13\cdot 17\cdot 421$ ，矛盾。

因此通过条件(1)和条件(2)的简单计算，我们可以排除 $p=31,41,43,61,71,113,421$ ，最后得到 $p=281$ 。

类似地，如果q整除 $\left(p-1\right)/2$ ，则 $p+1|840$ 或1120，其中 $p\ge 29$ 并且p是一个素数，我们有 $p=29,31,41,59,79,83,139,167,223,419,839$ 。更进一步地，计算还需要满足两个条件：

(1) $15pq|\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2$ 。

(2) $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right||840pq$ 或1120pq，其中 $p>q>5$ 是素数。

① 当 $p=29$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^2\cdot 3\cdot 5\cdot 7\cdot 29$ ，由q需要整除 $\left(p-1\right)/2=14$ ，且 $p>q>5$ 是素数，可得 $q=7$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 7\cdot 29$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 5\cdot 7\cdot 29$ ，矛盾。

② 当 $p=31$ 时，由q需要整除 $\left(p-1\right)/2=15$ ，与 $p>q>5$ 是素数矛盾。

③ 当 $p=41$ 时，由q需要整除 $\left(p-1\right)/2=15$ ，与 $p>q>5$ 是素数矛盾。

④ 当 $p=59$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^2\cdot 3\cdot 5\cdot 29\cdot 59$ ，由q需要整除 $\left(p-1\right)/2=29$ ，且 $p>q>5$ 是素数，可得 $q=29$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 29\cdot 59$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 5\cdot 29\cdot 59$ ，矛盾。

⑤ 当 $p=79$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^4\cdot 3\cdot 5\cdot 13\cdot 79$ ，由q需要整除 $\left(p-1\right)/2=39$ ，且 $p>q>5$ 是素数，可得 $q=13$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 13\cdot 79$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^4\cdot 3\cdot 5\cdot 13\cdot 79$ ，矛盾。

⑥ 当 $p=83$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^2\cdot 3\cdot 7\cdot 41\cdot 83$ ，由q需要整除 $\left(p-1\right)/2=41$ ，且 $p>q>5$ 是素数，可得 $q=41$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 41\cdot 83$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^2\cdot 3\cdot 7\cdot 41\cdot 83$ ，矛盾。

⑦ 当 $p=167$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^3\cdot 3\cdot 7\cdot 83\cdot 167$ ，由q需要整除 $\left(p-1\right)/2=83$ ，且 $p>q>5$ 是素数，可得 $q=83$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 41\cdot 83$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^3\cdot 3\cdot 7\cdot 83\cdot 167$ ，矛盾。

⑧ 当 $p=223$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^5\cdot 3\cdot 7\cdot 37\cdot 223$ ，由q需要整除 $\left(p-1\right)/2=111$ ，且 $p>q>5$ 是素数，可得 $q=37$ 。接下来，将 $p,q$ 的值代入条件(1)，此时 $35\cdot 111\cdot 223$ 不整除 $\left|T\right|=\left|\text{PSL}\left(2,p\right)\right|=2^5\cdot 3\cdot 7\cdot 37\cdot 223$ ，矛盾。

⑨ 当 $p=419$ 时，我们有 $\left|\text{PSL}\left(2,p\right)\right|=p\left(p-1\right)\left(p+1\right)/2=2^2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 19\cdot 419$ 。由q需要整除 $\left(p-1\right)/2=209$ ，且 $p>q>5$ 是素数，可得 $q=11$ 或19。将 $p,q$ 的值代入条件(2)，此时矛盾。

因此通过条件(1)和条件(2)的简单计算，我们可以排除 $p=29,31,41,59,79,83,167,223,419$ 。最后得到 $p=139,839$ 。

综上在这种情况下，我们有 $p=139,281,839$ 。因此，T的唯一可能是以下的单群： $\text{PSL}\left(2,139\right)$ ， $\text{PSL}\left(2,81\right)$ ， $\text{PSL}\left(2,839\right)$ 。

假设 $T\cong \text{PSL}\left(2,139\right)$ ，我们有 $q=23$ ， $p=139$ ，则 $V\left(\Gamma \right)=14pq=44758$ ，如果T在 $V\left(\Gamma \right)$ 上传递，则Γ是T-弧传递的，所以 $\left|T_{\alpha }\right|=\left|T\right|/44758=30$ ，根据引理2.4，这是不可能的。因此，T在 $V\left(\Gamma \right)$ 上恰好有两个轨道，当 $\text{Out}\left(\text{PSL}\left(2,139\right)\right)\cong Z_2$ 时，我们有 $\text{A}\cong \text{PGL}\left(2,139\right)$ ，则 $\left|{\text{A}}_{\alpha }\right|=\left|\text{A}\right|/44758=60$ 。通过Magma [18] 直接计算， $\Gamma \cong C_{44758}$ 。

假设 $T\cong \text{PSL}\left(2,281\right)$ ，我们有 $q=47$ ， $p=281$ ，则 $V\left(\Gamma \right)=184898$ ，当 $\text{Out}\left(\text{PSL}\left(2,281\right)\right)\cong Z_2$ 时， $\text{A}\cong \text{PSL}\left(2,281\right)$ 或 $\text{PGL}\left(2,281\right)$ ，于是 $\left|{\text{A}}_{\alpha }\right|=\left|\text{A}\right|/184898=60$ 或120，由Magma [18] 计算，在这种情况下没有五度对称图。

假设 $T\cong \text{PSL}\left(2,839\right)$ ，我们有 $q=419$ ， $p=839$ ，则 $V\left(\Gamma \right)=14pq=4921574$ ，当 $\text{Out}\left(\text{PSL}\left(2,839\right)\right)\cong Z_2$ 时， $\text{A}\cong \text{PSL}\left(2,839\right)$ 或 $\text{PGL}\left(2,839\right)$ ，于是 $\left|{\text{A}}_{\alpha }\right|=\left|\text{A}\right|/14pq=60$ 或120，由Magma [18] 计算，在这种情况下没有五度对称图。定理1.1的证明完成。

NOTES

^*通讯作者。