一类奇数阶4度非2-弧传递图的构造

A Construction of an Odd Order 4-Valent Non-2-Arc-Transitive Graph

摘要: 本文是在图的阶为奇数，度数为4的条件下，通过分析图$\Gamma$ 的自同构群的子群及其点稳定子群的结构，特别是弧传递图的相关理论和基本性质，利用特定顶点和度数的群的作用和图的对称性等相关理论，进一步探讨了这类图的存在性和结构特征，给出了一类奇数阶4度非2-弧传递图的构造。

Abstract: In this paper, under the condition of odd order and degree 4. By analyzing the structure of subgroups of the automorphism group of the graph and its point-stabilizer subgroups, especially relying on the relevant theories and basic properties of arc-transitive graphs, and making use of the group actions on specific vertices and degrees, as well as the theories related to the symmetry of the graph, the existence and structural characteristics of such graphs are further explored. A construction method for a class of odd-order 4-degree non-2-arc-transitive graphs is presented.

1. 引言

本文所讨论的图均为有限简单图。

令G是在顶点集V上的一个置换群，对于$\forall \alpha \in V$ ，使得$G_{\alpha }=\left\{g\in G|{\alpha }^g=\alpha \right\}$ ，则称$G_{\alpha }$ 为点稳定子群。点稳定子群有助于研究图的局部性质和自同构群的结构，通过点稳定子群可分析图在某个点附近的对称性和不变性质。并且，它可以应用在网络分析中，研究特定节点周围的网络结构稳定性；在化学中研究分子结构时，点稳定子群能帮助分析特定原子周围化学键和基团的对称性。

令图$\Gamma =\left(V,E\right)$ ，其中V为其顶点集，E为其边集。对于每一条边$\left\{\alpha ,\beta \right\}\in E$ ，其中包含了两条有序对$\left(\alpha ,\beta \right)$ 与$\left(\beta ,\alpha \right)$ ，称为图$\Gamma$ 的弧。称$\left(\alpha ,\beta ,\gamma \right)$ 为图$\Gamma$ 的2-弧，若$\alpha \ne \gamma$ 且$\left(\alpha ,\beta \right)$ 与$\left(\beta ,\gamma \right)$ 均为$\Gamma$ 的弧。同时，我们用$\Gamma \left(\alpha \right)$ 表示在$\Gamma$ 中与顶点$\alpha$ 相邻的点的集合，即顶点$\alpha$ 的邻域，图的度数为$\left|\Gamma \left(\alpha \right)\right|$ 。本文中所研究的4度图是指每个顶点的度数都为4。

设图${\Gamma }_1=\left(V_1,E_1\right)$ 和图${\Gamma }_2=\left(V_2,E_2\right)$ ，如果存在一个双射$g:V_1\to V_2$ ，使得对于任意的$\alpha ,\beta \in V_1$ ， $\left\{\alpha ,\beta \right\}\in E_1$ 有$\left\{{\alpha }^g,{\beta }^g\right\}\in E_2$ ，则称图${\Gamma }_1$ 和图${\Gamma }_2$ 同构；称顶点集V上的一个置换m为图$\Gamma$ 的自同构，当且仅当对于所有的$\left\{\alpha ,\beta \right\}\in E$ ，存在$\left\{{\alpha }^m,{\beta }^m\right\}\in E$ 。图$\Gamma$ 的所有自同构在置换乘法下组成一个群，叫做图$\Gamma$ 的自同构群，记作$Aut\Gamma$ 。令G是$Aut\Gamma$ 的一个子群，若G作用在图$\Gamma$ 的顶点集V、边集E、弧集A上是传递的，则称图$\Gamma$ 是G-点传递、G-边传递、G-弧传递；同理，若$Aut\Gamma$ 在顶点集V、边集E、弧集A上是传递的，则相应地称图$\Gamma$ 是点传递、边传递、弧传递的。因此图的自同构群反映了图的对称性，可用于对图进行分类，相同自同构群结构的图可能具有相似的性质和特征。在网络结构中，可通过分析网络的自同构群能了解网络对称性，帮助优化网络布局和资源分配；在密码学中，基于图自同构问题的困难性可构造公钥密码体制。

因此，基于以上的知识可知，若通过群的作用能将图中任意两个顶点连接起来，那么这个图是连通的；从群作用的角度分析顶点之间的关系，有助于判断图的连通性以及理解连通分支的结构。而图的对称性由自同构群来刻画，若存在自同构使得某个子图映射到自身，则这个子图是一个不变子图；通过寻找图的不变子图，可以将图分解为具有特定对称性的子结构，有助于分析图的整体结构。

对于$s\ge \text{1}$ ，定义了在图$\Gamma$ 上的s-弧，即是一个(s + 1)-元序列$\left({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_s\right)$ ，其中${\alpha }_i\in V$ ，满足 $\left\{{\alpha }_i,{\alpha }_{i+1}\right\}\in E$ 和${\alpha }_i\ne {\alpha }_{i+2}$ ，$\text{1}\le i\le s$ ；进一步，如果G在s-弧集上传递，但在(s + 1)-弧集上不传递，则称$\Gamma$ 是(G,s)-传递图。R. Weiss在文献[1]中证明了不存在6传递图和8以上的s-传递图，即$s=\left\{\text{1},\text{2},\text{3},\text{4},\text{5},\text{7}\right\}$ 。

在过去的80多年里，群与图已经发展成为代数图论的一个重要领域，并且针对刻画某一类特征的图先后出现了许多精彩的理论。事实上，当我们对图进行分类时，通常是对它的顶点数或者度数进行限制，比如Conder在文献[2]中主要研究了度数 ≥ 4时的弧传递图和2-弧传递图的阶数问题，为4度图的深入研究提供了参考；还有当图的顶点数为奇数时，李才恒教授等人在文献[3]中对4度边传递Cayley图进行了完全的分类；其中，弧传递图作为一类具有高度对称性的图，一直是研究热点之一。例如Tutte在文献[4]，证明了所有3度弧传递图都是s-弧传递图，其中$s\le \text{5}$ ；在文献[5]中，李才恒教授等人对在局部本原的条件下度数为5，6，7的弧传递图进行了详细的研究；以上都为弧传递图的分类奠定了基础，比如，李才恒教授等人在文献[6]中对弧传递图及其自同构群进行了完整的刻画。因此可以体现出弧传递图在图论研究中是重要的研究对象。因为其结构和性质相对较为规则，所以可作为构建其他复杂图结构的基础；在通信网络中，弧传递图可用于设计高效的路由算法和网络拓扑结构；在多主体系统中，可用于建模主体间具有对称交互关系的系统。

称$\Gamma$ 是点本原的，如果G在顶点集V上的作用是本原的，即不存在非平凡的不变划分。点本原图是一类具有特殊性质的图，其研究对于理解图的对称性、结构性质以及群与图之间的相互作用有着重要意义，所以点本原图在代数图论中成为研究的重点对象之一，比如Praeger在文献[7]中对所有kp阶的点本原、边传递图进行了分类(其中k、p为素数)；在文献[8]中，李才恒教授对s ≥ 4的点本原图进行了完全的分类。

基于此，本文的主要目的是刻画一类在某些限制条件下的点本原非2-弧传递图。

定理1.1 设$\Gamma =\left(V,E\right)$ 是一个pq阶4度的非2-弧传递连通图，其中p，q均为素数。令$G\le Aut\Gamma$ ，且G是几乎单群，作用在顶点集V上是本原的。进一步，若$\Gamma$ 是G-边传递的，则图$\Gamma$ 在同构意义下是唯一存在的，且$\Gamma =\mathrm{Cos}\left(G,H,HxH\right)$ ，其中$G=PG{L}_2\left(7\right)$ ，$H\cong D_{16}$ 。

2. 预备知识

引理2.1. [9] 设N为G在V上传递的极小正规子群，则N具有唯一性。

引理2.2. 如果一个图$\Gamma$ 是G-弧传递的，则$G_{\alpha }$ 在$\Gamma \left(\alpha \right)$ 上传递。

证明：令${\beta }_1,{\beta }_2,\cdots ,{\beta }_i,\cdots ,{\beta }_j\in \Gamma \left(\alpha \right)$ ，则$\left(\alpha ,{\beta }_1\right),\left(\alpha ,{\beta }_2\right),\cdots ,\left(\alpha ,{\beta }_i\right),\cdots ,\left(\alpha ,{\beta }_j\right)$ 为$\Gamma$ 的弧；由于$\Gamma$ 是G-弧传递的，所以存在$g\in G$ ，使得${\left(\alpha ,{\beta }_1\right)}^g=\left({\alpha }^g,{\beta }_1^g\right)=\left(\alpha ,{\beta }_2\right)$ ，则有${\alpha }^g=\alpha$ ，${\beta }_1^g=\beta$ ；同理${\alpha }^g=\alpha$ ，${\beta }_1^g={\beta }_2$ ；$\cdots$ ；${\alpha }^g=\alpha$ ，${\beta }_i^g={\beta }_j$ 。于是可知g固定$\alpha$ ，故可得到$g\in G_{\alpha }$ ；再根据i，j的任意性，可知$G_{\alpha }$ 在$\Gamma \left(\alpha \right)$ 上是传递的。

接下来，我们考虑有向图$\Delta =\left(V,A\right)$ ，其中A为弧集。在此情形下，$\Delta$ 是一个无向图，当且仅当$A=A^{*}$ ，其中$A^{*}=\left\{\left(\alpha ,\beta \right)|\left(\beta ,\alpha \right)\in A\right\}$ 。

我们设$\Delta =\left(V,A\right)$ 是一个有向图，且$G\le Aut\Delta$ ，令$\Delta \left(\alpha \right)=\left\{\beta \in V|\left(\alpha ,\beta \right)\in A\right\}$ 表示顶点$\alpha$ 的邻域。于是，对于G的每一个正规子群N，点稳定子群$N_{\alpha }$ 在$\Delta \left(\alpha \right)$ 上诱导了一个置换群，记为$N_{\alpha }^{\Delta \left(\alpha \right)}$ 。同时，我们用$N_{\alpha }^{\left[1\right]}$ 来表示$N_{\alpha }$ 作用在$\Delta \left(\alpha \right)$ 上的核，于是我们有下面的简单结论：

(1) $N_{\alpha }^{\Delta \left(\alpha \right)}\cong N_{\alpha }/N_{\alpha }^{[1]}$ ，$N_{{\alpha }^g}={\left(N_{\alpha }\right)}^g$ ，$N_{{\alpha }^g}^{\left[1\right]}={\left(N_{\alpha }^{\left[1\right]}\right)}^g$ ，$\Delta \left({\alpha }^g\right)=\Delta {\left(\alpha \right)}^g$ ，$\forall g\in G$ 。

对于有限群H，我们用$\pi \left(H\right)$ 来表示$\left|H\right|$ 中全体素因子的集合。下面的引理告诉我们当$\Delta$ 是连通的、G-点传递图时，$\pi \left(N_{\alpha }\right)=\pi \left(N_{\alpha }^{\Delta \left(\alpha \right)}\right)$ 。

引理2.3. [9] 设$\Delta =\left(V,A\right)$ 为有向连通图，令$G\le Aut\Delta$ ，N是G的正规子群，若G作用在V上传递，则$\pi \left(N_{\alpha }\right)=\pi \left(N_{\alpha }^{\Delta \left(\alpha \right)}\right)$ ，并且要么$\pi \left(G_{\alpha }^{\left[1\right]}\right)\subseteq \pi \left(N_{\alpha }\right)$ ，要么N作用在V上不传递。

对于群的Cayley图，我们知道Cayley图一定是点传递图，但点传递图不一定都是Cayley图。Sabidussi在1964年给出了另一种用群来构造点传递图的方法，叫做陪集图。与Cayley图不同的是，每个点传递图都可以经过适当的构造变成陪集图。首先我们给出陪集图的定义。

定义2.4. [10] 设G是有限群，H是G的一个子群，设S是若干个形如HgH的双陪集的并集，其中$g\notin H$ ，则G关于H和S的陪集图$\Gamma =\mathrm{Cos}\left(G,H,S\right)$ 定义如下：

顶点集$V\left(\Gamma \right)=\left[G:H\right]$ (H在G中的所有左陪集的集合)

边集$E\left(\Gamma \right)=\left\{\left\{Hx,Hy\right\}|y{x}^{-1}\in S\right\}$ ，

由此定义易知，当H = 1时，此时的陪集图即为Cayley图。关于陪集图，下面的命题是基本的。

命题2.5. [11] [12] 设$\Gamma =\mathrm{Cos}\left(G,H,S\right)$ 是G关于H和S的陪集图，则有

(1) $\Gamma$ 是连通图，当且仅当$\langle S\rangle =G$ ；

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

(3) $\Gamma$ 是G-弧传递的，当且仅当存在$x\in G\backslash H$ ，使得$S=HxH$ 且$x^2\in H$ 。

最后我们给出4度点本原图的分类结果。

引理2.6. [13] 若图$\Gamma$ 是n阶4度点本原s-传递图，那么$\Gamma$ 同构于下列若干情形之一，其中s，n和$Aut\Gamma$ 如表1所示。

Table 1. 4-Valent vertex primitive arc-transitive Graph

表1. 4度点本原弧传递图

$Aut\Gamma$	Vertex-stabiliser	s
$Z_p:Z_4$	$Z_4$	1
$Z_p^2:D_8$	$D_8$	1
$PS{L}_2\left(p\right)$	$S_4$	2
$PS{L}_2\left(p\right)$	$A_4$	2
$PG{L}_2\left(p\right)$	$S_4$	2
$PG{L}_2\left(7\right)$	$D_{16}$	1
$Aut\left(A_6\right)$	$\left[2^5\right]$	1
$PS{L}_2\left(17\right)$	$D_{16}$	1
$S_7$	$S_4\times S_3$	3
$PS{L}_3\left(7\right)$	$\left(A_4:Z_3\right):Z_2$	3

3. 定理1.1的证明

在本节中，我们设$\Gamma =\left(V,E\right)$ 是一个pq阶的4度连通图，p，q均为素数并且图$\Gamma$ 是非2-弧传递的。令$G\le Aut\Gamma$ ，G是几乎单群且满足G作用在边集E上是传递的，作用在顶点集V上是本原的。由于$\left|V\right|$ 是奇数，于是根据文献[14]对于奇数阶本原群的分类结果，我们可以确定群G的结构。

由文献[13]可知，$\Gamma$ 是弧传递的，结合$\Gamma$ 是非2-弧传递的，所以可知$\Gamma$ 是1-传递图，即对应表1中s = 1的情况。因此结合引理2.6可知图$\Gamma$ 的结构可能有5种情形。进一步，我们假设G是几乎单群，令N为G的极小正规子群，结合G的本原性，于是N为非交换单群且N作用在V上是传递的。根据引理2.1可知，N是G的唯一极小正规子群，于是N = soc(G)。又因为$\left|V\right|$ 是奇数，点稳定子群$N_{\alpha }\ne 1$ ，故由引理2.3可知$N_{\alpha }^{\Gamma \left(\alpha \right)}\ne 1$ 。

注意到$\Gamma$ 是1-传递的，因此由表1可知$Aut\Gamma \cong PG{L}_2\left(7\right)$ ，$Aut\left(A_6\right)$ 或者$PS{L}_2\left(17\right)$ 。进一步，由文献[9]可知，G和$Aut\Gamma$ 的极小正规子群相同，即$N=soc\left(G\right)=soc\left(Aut\Gamma \right)$ 。下面我们逐一分析其可能性。若$G\cong Aut\left(A_6\right)$ ，注意到$Aut\left(A_6\right)\cong P\Gamma L_2\left(9\right)$ ，结合$G_{\alpha }\cong \left[2^5\right]$ 可知

$\left|V\right|=\left|G\right|/G_{\alpha }=\left|P\Gamma L_2\left(9\right)\right|/\left[2^5\right]=\frac{1440}{32}=45=3^2\times 5$ ，与条件$\left|V\right|=pq$ 矛盾；若$G\cong PS{L}_2\left(17\right)$ ，则此时$G_{\alpha }\cong D_{16}$ ，于是$\left|V\right|=\left|G\right|/G_{\alpha }=\left|PS{L}_2\left(17\right)\right|/\left|D_{16}\right|=\frac{2448}{16}=153=3^2\times 17$ ，与条件$\left|V\right|=pq$ 矛盾；若$G=PG{L}_2\left(7\right)$ ，$G_{\alpha }\cong D_{16}$ ，于是$\left|V\right|=\left|G\right|/G_{\alpha }=\left|PG{L}_2\left(17\right)\right|/\left|D_{16}\right|=\frac{336}{16}=21=3\times 7$ ，满足条件。

于是接下来，我们将以$G=Aut\Gamma \cong PG{L}_2\left(7\right)$ 来构造满足条件的图。我们先来计算满足条件所需的群的构造。

令$G=PG{L}_2\left(7\right)$ ，则此时$N=soc\left(G\right)=PS{L}_2\left(7\right)$ ，同时令$H\cong D_{16}=G_{\alpha }\le G$ ，再令$K\cong Z_2^2$ ，由于 $Z_2^2\le S_4\le PS{L}_2\left(7\right)$ 且$Z_2^2\le D_{16}$ ，于是$K\le H\cap N$ 。由于$H\cong D_{16}$ ，于是我们可设 $H=\langle r,s|r^8=s^2=1,srs=r^{-1}\rangle$ ，且$K=\langle r^4\rangle \times \langle r^4\rangle$ ，于是$N_H\left(K\right)=\langle r^2,s\rangle$ ，其结构满足$D_8$ 的定义即 $\langle a,b|a^4=b^2=1,bab=a^{-1}\rangle$ ，所以$N_H\left(K\right)\cong D_8$ ；并且利用MAGMA计算可知$N_G\left(K\right)=N_N\left(K\right)\cong S_4$ 。

最后，我们来构造满足条件的陪集图。

取一个对合$x\in N_N\left(K\right)\backslash H$ ，即在$N_N\left(K\right)\backslash H$ 中，满足$x^2=e$ ，其中e是单位元。于是我们可令 $\Gamma =\mathrm{Cos}\left(G,H,HxH\right)$ ，顶点集为G中H的右陪集的集合，即$V\Gamma =\left\{Hg|g\in G\right\}$ ；边集由形如$\left\{H{g}_1,H{g}_2\right\}$ 的无序对组成，其中$g_1^{-1}{g}_2\in HxH$ ；利用MAGMA计算可知$\langle H,x\rangle =G$ ，因此由命题2.5可知$\Gamma$ 是连通图。

由已知可得$\left|G\right|=\left|PG{L}_2\left(7\right)\right|=\left(7^2-1\right)\times 7=336$ ，$\left|H\right|=\left|D_{16}\right|=16$ ，$\left|HxH\right|=\frac{\left|H\right|\times \left|H\right|}{\left|H\cap x^{-1}Hx\right|}=\frac{16\times 16}{4}=64$ 则其顶点数为$\left|V\Gamma \right|=\left|G:H\right|=\frac{\left|G\right|}{\left|H\right|}=21$ ，即顶点数为奇数，度数为$\left|HxH:H\right|=\frac{\left|HxH\right|}{\left|H\right|}=4$ 。再结合$x^2=1\in H$ 可知$\Gamma$ 是一个连通的21阶、4度的弧传递图。

根据H的取法可知H是G的极大子群，由本原性的判别法则可知G是本原的，因此上述的陪集图$\Gamma$ 是点本原的。故由前面分析可知，存在唯一的一个21阶、4度点本原弧传递图满足我们的条件。

至此我们就完成了主要定理的证明。