一类3度弧正则Cayley图

A Family of Arc-Regular Cubic Cayley Graphs

摘要: 称一个图是弧正则的，如果其全自同构群在其弧集上的作用是正则的。Xu引出问题：是否存在一个3度弧正则图，其全自同构群是不可解的。本文我们运用群论的相关知识，构造了一类3度弧正则Cayley图，并决定了此类图的全自同构群，从而得到了满足上述问题的3度弧正则图。

Abstract: A graph is called arc-regular, if its automorphism group acts regularly on its arc set. Xu introduces a question: whether there is an arc-regular cubic graph with an insolvable automorphism group. In this paper, we apply the related knowledge of group theory to construct a family of arc-regular cubic Cayley graphs and determine its automorphism group, consequently obtaining arc-regular cubic graphs that satisfy the above problems.

1. 引言

本文讨论的图是有限无向的，无自环和重边。

本文采用标准的符号和术语，可参考 [1] [2]。如用 ${\text{A}}_n$ 和 ${\text{S}}_n$ 分别表示n次的交错群和对称群， ${\mathbb{Z}}_n$ 表示n阶循环群。对于两个群N和H，我们用 $N\times H$ 表示N和H的直积，用 $N\text{.}H$ 表示N被H扩张，如果这个扩张是可裂的，则记为 $N:H$。对有限群G，通过 $Z\left(G\right)$ 和 $C_G\left(H\right)$ 分别表示G的中心和H在G中的中心化子。对群T和集合D上的置换群L，用 $T\wr L$ 表示T和L的圈积。用 $\text{Aut}\left(T\right)$ 表示为群T的全自同构群。

对于一个非空图 $\Gamma$，我们用 $V\Gamma$， $E\Gamma$， $A\Gamma$ 和 $\text{Aut}\left(\Gamma \right)$ 分别表示它的顶点集、边集、弧集和全自同构群，记 $\left|V\Gamma \right|$ 为图 $\Gamma$ 的阶。给定顶点 $\alpha \in V\Gamma$，与顶点 $\alpha$ 邻接的点集称为 $\alpha$ 的邻域，记为 $\Gamma \left(\alpha \right)$， $\left|\Gamma \left(\alpha \right)\right|$ 称为点 $\alpha$ 的度数。我们称顶点集的一个 $s+1$ 序列 $\left({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_s\right)$ 为 $\Gamma$ 的一条s-弧，如果任意相邻两点邻接且 ${\alpha }_{i+1}\ne {\alpha }_{i-1}$，其中 $1\le i\le s-1$。

设 $X\le \text{Aut}\left(\Gamma \right)$。那我们称图 $\Gamma$ 为X-点传递图、X-边传递图、X-弧传递图或 $\left(X,s\right)$ -弧传递图，如果X分别在 $V\Gamma$ 、 $E\Gamma$ 、 $A\Gamma$ 上传递。类似地称 $\Gamma$ 为X-弧正则图，如果X在 $A\Gamma$ 上正则。特别地，如果 $\text{Aut}\left(\Gamma \right)$ 在 $A\Gamma$ 上正则，则称 $\Gamma$ 为弧正则图。Cayley图 [3] 是一类重要的点传递图，对给定的群G和它的子集S，有 $S=S^{-1}=\left\{g^{-1}|g\in S\right\}$ 且 $1\notin S$。可以定义群G上的Cayley图如下：顶点集为G，顶点g与h是邻接的当且仅当 $h{g}^{-1}\in S$，将这个图记为 $\text{Cay}\left(G,S\right)$。众所周知，一个图 $\Gamma$ 是群G上的Cayley图当且仅当 $\text{Aut}\left(\Gamma \right)$ 中包含一个顶点集上的正则子群G。

弧正则图的分类和构造受到了许多学者们的关注，是代数图论方向上一个热门课题。例如：R. Frucht [4] 1952年构造了第一个弧正则图，该图是432阶3度图。值得一提的是，1997年Marušič和Xu [5] 证明了3度弧正则图的线图同构于一个围长为3的4度半弧传递图，这为构造半弧传递图提供了新的方法，因此这也是本文研究3度弧正则图的动机之一。下面介绍一些小度数弧正则图的例子。例如1997年，Marušič [6] 给出了单群 ${\text{A}}_n$ 上的4度弧正则Cayley图( $n\ge 5$ 是奇数)；2000年Marušič和Pisanski [7] 给出了二面体群上的3度弧正则Cayley图；2002年Fang，Wang和Xu [8] 研究了G为可解群下的G-弧正则图，并且构造了两类具有不可解自同构群的3度弧正则图；2006年Kwak和Oh [9] 给出了一类二面体群上的4度和6度弧正则图；2012年，Conder和Feng [10] 给出了一类非交换单群 $PSL\left(2,p^3\right)$ 上的3度弧正则Cayley图(p为奇素数)。此外，许多学者也对具有特定的阶和度数的弧正则图进行了深入研究。如2004年，Feng和Kwak [11] 刻画了阶为2p或 $2p^2$ 的3度弧正则图(p为素数)；2009年Zhou和Feng [12] 分类了2pq阶的4度弧正则图(p和q为素数)；2018年Ding [13] 分类了平方自由阶素数度的2-弧正则图；2021年Wang和Gao [14] 分类了平方自由阶 $\left(G,2\right)$ -弧正则图，其中G是几乎单群。更多的研究成果，读者可参见文献 [15] [16] [17] [18] [19]。

下面首先介绍本文的主要结论。

定理1.1 设T是一个“WG”-单群(见下文定义2.1)，令群 $X\cong T\wr {\mathbb{Z}}_3$。设群 $G\cong T^3$ 为X唯一的极小正规子群，则存在群G上的3度Cayley图 $\Gamma$，并且图 $\Gamma$ 具有以下性质：

1) $\Gamma$ 为连通的X-弧正则图。

2) $\text{Aut}\left(\Gamma \right)=X$。

注：a) 定理1.1中图 $\Gamma$ 的存在性见第三节的构造，其构造也进一步回答了 [8]：存在无穷多的3度弧正则图，其全自同构群是不可解的。

b) 设图 $\Sigma$ 为 $\Gamma$ 的线图，由文献 [6] 可知， $\Sigma$ 是一个4度的半弧传递图并且有 $\text{Aut}\left(\Gamma \right)=\text{Aut}\left(\Sigma \right)$，于是我们也构造出了一个无穷类的4度半弧传递图。

本文结构如下：在第二节，给出一些群论和图论的相关定义和引理。在第三节，给出定理1.1中图的构造和该图性质的证明，见构造，引理3.1，引理3.2和引理3.4。

2. 预备知识

在本节，我们先介绍主要定理中“WG”-单群的概念，其性质直接决定了图 $\Gamma$ 的性质。此概念是我们新引入的，“WG”是“well-generated”的简写。

定义2.1交换单群T是“WG”-单群，如果T满足下面条件：

1) $T=\langle t_1,t_2,t_3\rangle$，其中 $t_1,t_2,t_3\in T$ 都是2阶元。

2) 不存在 $\eta \in \text{Aut}\left(T\right)$ 使得 $t_1^{\eta }=t_2\text{,}{t}_2^{\eta }=t_3\text{,}{t}_3^{\eta }=t_1$ 成立。

3) 对任意的i = 1, 2, 3都不存在 ${\sigma }_i\in \text{Aut}\left(T\right)$ 使得 $t_i^{{\sigma }_i}=t_i$ 并且 ${\sigma }_i$ 对换剩余的两个2阶元。

注：存在无穷多的“WG”-单群，如Nuzhin [20] 构造了单群 ${\text{A}}_n\left(n\ge 5\right)$ 可以由三个2阶元生成，其中两个2阶元可以交换。经过简单的验证可以知道 ${\text{A}}_n\left(n\ge 5\right)$ 也满足上述定义的(2)，(3)。故不可解的交错群都是“WG”-单群。这类能由3个2阶元生成的单群已经得到广泛研究，例如对于某些Hurwitz单群也满足我们“WG”-单群的定义，可参考文献 [21]。

下面我们先介绍Cayley图的全自同构群的两个重要子群。

设图 $\Gamma =\text{Cay}\left(G,S\right)$ 为群G在集合S上的Cayley图，令两个群为 $\hat{G}=\left\{\hat{g}|\hat{g}:x\mapsto xg,\forall x,g\in G\right\}$ 和 $\text{Aut}\left(G,S\right)=\left\{\beta \in \text{Aut}\left(G\right)|S^{\beta }=S\right\}$。容易知道 $\hat{G}$ 和 $\text{Aut}\left(G,S\right)$ 都是 $\text{Aut}\left(\Gamma \right)$ 的子群，并且 $\hat{G}$ 在顶点集G上作用正则。于是在不引起误会的情况下，可将 $\hat{G}$ 记为G。

引理2.2 [3] 设 $\Gamma =\text{Cay}\left(G,S\right)$，则 $\Gamma$ 是连通图当且仅当 $G=\langle S\rangle$。那么如果 $\Gamma$ 是连通图，则群 $\text{Aut}\left(G,S\right)$ 忠实地作用在S上。

正规Cayley图的概念，最早由Xu [22] 提出，这是一类特殊的Cayley图。

定义2.3设图 $\Gamma =\text{Cay}\left(G,S\right)$，其中 $G\le X\le \text{Aut}\left(\Gamma \right)$。我们称 $\Gamma$ 是X-正规Cayley图，如果满足 $G⊲X$。特别地，如果 $G⊲\text{Aut}\left(\Gamma \right)$，则称 $\Gamma$ 为正规Cayley图。

正规Cayley图的自同构群有较好的刻画，其具有如下性质：

引理2.4 [1] 设 $\Gamma =\text{Cay}\left(G,S\right)$ 是连通的，记 $N=N_{\text{Aut}\left(\Gamma \right)}\left(G\right)$。则 $N=G:\text{Aut}\left(G,S\right)$。特别地，如果 $\Gamma$ 是正规Cayley图，则 $\text{Aut}{\left(\Gamma \right)}_1=\text{Aut}\left(G\text{,}S\right)$，1是G中单位元代表的顶点。

下面介绍连通的3度 $\left(G\text{,}s\right)$ -弧传递图的点稳定子群结构。

引理2.5 [23] 设图 $\Gamma$ 为一个连通的3度 $\left(G\text{,}s\right)$ -弧传递图，则 $s\le 5$。任意 $\alpha \in V\Gamma$，则 $\left(G_{\alpha }\text{,}s\right)$ 为以下情形之一： $\left({\mathbb{Z}}_{\text{3}},1\right)$， $\left({\text{S}}_3,2\right)$， $\left({\text{S}}_3\times {\mathbb{Z}}_2,3\right)$， $\left({\text{S}}_{\text{4}},4\right)$， $\left({\text{S}}_4\times {\mathbb{Z}}_2,5\right)$。

最后我们以有限群论的一个经典结果来结束本节。

引理2.6设群G有一个指数为k的子群H，令 $C=\underset{g\in G}{\cap }{H}^g$ (称为H在G中的核)。则C为含在H中G的最大正规子群，并且 $G/C\le {\text{S}}_k$。特别地， $G\le {\text{S}}_k$，如果H在G中的核为1。

3. 构造和证明

在本节，我们首先给出定理1.1中图的构造。

构造：设T是一个“WG”-单群。由 定义2.1 可知，可记 $T=\langle t_1,t_2,t_3\rangle$， $t_1,t_2,t_3$ 为2阶元。下令群 $X\cong T\wr {\mathbb{Z}}_3$。设G为X唯一的极小正规子群，则我们有 $G\cong T^3$ 且 $X\cong G:\langle \tau \rangle$，其中 $\tau$ 是3阶元使得 ${\left(g_1,g_2,g_3\right)}^{\tau }=\left(g_2,g_3,g_1\right)$，其中元素 $g_1,g_2,g_3\in T$。

下设 $s_1=\left(t_1,t_2,t_3\right)\text{,}{s}_2=s_1^{\tau }\text{,}{s}_3=s_1^{{\tau }^2}$，取集合 $S=\left\{s_1,s_2,s_3\right\}$，记 $\Gamma =\text{Cay}\left(G,S\right)$。

后面证明中的符号和术语均与上述构造所一致。

引理3.1 $\Gamma$ 是X-弧正则的3度Cayley图， $X\le \text{Aut}\left(\Gamma \right)$。

证明 由于 $\tau \in \text{Aut}\left(G,S\right)$，将G视为G我们可得 $X=G:\langle \tau \rangle$ 是 $\text{Aut}\left(\Gamma \right)$ 的子群。由于 $\langle \tau \rangle$ 在 $\Gamma \left(1\right)=S$ 上传递，那么 $\Gamma$ 是X-弧传递的。又由 $\left|X\right|=3\left|G\right|=\left|A\Gamma \right|$，可得 $\Gamma$ 是X-弧正则图的。

引理3.2 $\Gamma$ 是连通的。

证明 由引理2.2可知，只需证明： $G=\langle s_1,s_2,s_3\rangle$。按照顺序记G的3个直积因子分别为 $T_1,T_2,T_3$。设 $R=\langle s_1,s_2,s_3\rangle$。由于 $T=\langle t_1,t_2,t_3\rangle$，那么R在每个直积因子上的投影是满的，于是R是单群T的次直积(subdirect product)，见 [24]。如果 $R<G$，则R至少在两个分量上的投影是相连的(linked)。假设第一个分量和第二个分量相连，则存在自同构 $\sigma \in \text{Aut}\left(T\right)$ 使得 $t_1^{\sigma }=t_2\text{,}{t}_2^{\sigma }=t_3\text{,}{t}_3^{\sigma }=t_1$。这与T是“WG”-单群矛盾。假设第一个分量和第三个分量相连，则存在 ${\sigma }_1\in \text{Aut}\left(T\right)$ 使得 $t_1^{{\sigma }_1}=t_3\text{,}{t}_3^{{\sigma }_1}=t_2\text{,}{t}_2^{{\sigma }_1}=t_1$，也是矛盾。同理可证第二个分量和第三个分量也不相连，于是 $G=R$。

引理3.3 $G⊲\text{Aut}\left(\Gamma \right)$。

证明 假设G不是 $\text{Aut}\left(\Gamma \right)$ 的正规子群。由G是X唯一的非平凡正规子群，则由引理2.6可知，X在 $\text{Aut}\left(\Gamma \right)$ 中的核为1，故 $\text{Aut}\left(\Gamma \right)\le {\text{S}}_k$，其中 $k=\left|\mathrm{Aut}\left(\Gamma \right):X\right|$。注意到 $\text{Aut}\left(\Gamma \right)$ 和X都在顶点集合上传递，于是可得： $\left|\text{Aut}\left(\Gamma \right):X\right|=\left|\text{Aut}{\left(\Gamma \right)}_1:X_1\right|$。由 $X_1\cong {\mathbb{Z}}_3$ 和引理2.5我们可知，正整数k整除16。于是 $\text{Aut}\left(\Gamma \right)\le {\text{S}}_k\le {\text{S}}_{16}$。假设 $k\le 8$，由于 $\left|{\text{S}}_8\right|=2^7\cdot 3^2\cdot 5\cdot 7$，故 $\text{Aut}\left(\Gamma \right)$ 中不可能包含同构于 $T^3$ 的子群，矛盾。故 $k=16$ 并且 $\text{Aut}{\left(\Gamma \right)}_1\cong {\text{S}}_4\times {\text{S}}_2$。由于 $G=T^{\text{3}}\le \text{Aut}\left(\Gamma \right)\le {\text{S}}_{\text{16}}$ 并且 $\left|{\text{S}}_{\text{16}}\right|=2^{\text{15}}\cdot 3^{\text{6}}\cdot 5^{\text{3}}\cdot 7^{\text{2}}\cdot \text{11}\cdot \text{13}$，计算G的阶可知非交换单群T只可能为 ${\text{A}}_5$。于是可得图的全自同构群 $\text{Aut}\left(\Gamma \right)=G\text{.Aut}{\left(\Gamma \right)}_1\cong {\text{A}}_5^3.\left({\text{S}}_4\times {\text{S}}_2\right)$。根据 [25]，可推导出 ${\text{S}}_{16}$ 中不可能含有结构为 ${\text{A}}_5^3.\left({\text{S}}_4\times {\text{S}}_2\right)$ 这样的子群，矛盾。

在上述引理的基础上，最后我们证明本文最后一个关键性结论。

引理3.4 $\text{Aut}\left(\Gamma \right)=X$。

证明 记 $A=\text{Aut}\left(\Gamma \right)$。由引理3.3和引理2.4知 $A_1=\text{Aut}\left(G,S\right)$，并且由引理3.2和引理2.2知 $A_{\text{1}}$ 忠实作用在S上。故 $A_1\cong {\mathbb{Z}}_3$ 或 ${\text{S}}_3$。假设 $A_1\cong {\text{S}}_3$。更进一步假设 $C_A\left(G\right)\ne 1$。由于 $Z\left(G\right)=1$，则有 $G\cap C_A\left(G\right)=1$。设 $L=G\times C_A\left(G\right)$。则 $L⊲A$ 并且 $L=G{L}_1$。于是 $C_A\left(G\right)\cong L/G\cong L_1⊲A_1$，于是可得 $C_A\left(G\right)\cong {\mathbb{Z}}_3$。因此 $\left|L\right|=\left|X\right|=3\left|G\right|$。假设 $L\ne X$，则由 $\left|A:X\right|=2$，我们有 $LX=A$。故可得 $\left|X:X\cap L\right|=2$，这与X只有唯一的非平凡正规子群G矛盾。于是 $C_A\left(G\right)=1$。此时可得： $A_1\le \text{Aut}\left(G\right)=\text{Aut}\left(T\right)\wr {\text{S}}_3$。注意到 $X_1=\langle \tau \rangle ⊲A_1$，我们设 $A_1=\langle \tau \rangle :\langle \xi \rangle$， ${\tau }^{\xi }={\tau }^{-1}$， $\xi$ 为2阶元。由 $\tau$ 的定义(见构造)，可记 $\tau =\left(123\right)\in {\text{S}}_3$ 和 $\xi =\sigma \left({\xi }_1,{\xi }_2,{\xi }_3\right)$，其中 ${\xi }_1,{\xi }_2,{\xi }_3\in \text{Aut}\left(T\right)$ 且 $\sigma \in S_3$。由 ${\xi }^2={\sigma }^2{\left({\xi }_1,{\xi }_2,{\xi }_3\right)}^{\sigma }\left({\xi }_1,{\xi }_2,{\xi }_3\right)=1$ (记等式为 $E_1$ )，于是 $\sigma$ 是2阶元， ${\tau }^{\sigma }={\tau }^{-1}$。又由 ${\tau }^{\xi }={\tau }^{-1}$，所以 ${\tau }^{-1}={\tau }^{\xi }={\tau }^{\sigma \left({\xi }_1,{\xi }_2,{\xi }_3\right)}={\left({\tau }^{-1}\right)}^{\left({\xi }_1,{\xi }_2,{\xi }_3\right)}$。因此 ${\tau }^{-1}$ 与 $\left({\xi }_1,{\xi }_2,{\xi }_3\right)$ 交换，我们可推导出 ${\xi }_1={\xi }_2={\xi }_3$。再结合等式 $E_1$，我们可得 ${\xi }_1$ 是2阶元。由 $A_1=\langle \tau \rangle :\langle \xi \rangle$ 和 $\langle \tau ,\sigma \rangle ={\text{S}}_3$，则 $A_1$ 中所有的2阶元为： $\left(12\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right),\left(13\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right),\left(23\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right)$。由于 $A_1\cong {\text{S}}_3$ 中稳定 $s=\left(t_1,t_2,t_3\right)$ 的点是2阶元，于是有 ${\left(t_1,t_2,t_3\right)}^{\left(12\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right)}=\left(t_2^{{\xi }_1},t_1^{{\xi }_1},t_3^{{\xi }_1}\right)=\left(t_1,t_2,t_3\right)$，则 $t_3^{{\xi }_1}=t_3\text{,}{t}_1^{{\xi }_1}=t_2\text{,}{t}_2^{{\xi }_1}=t_1$，这与T是“WG”-群矛盾。同样的原理可说明 $\left(13\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right)$ 和 $\left(23\right)\left({\xi }_1,{\xi }_1,{\xi }_1\right)$ 都不能稳定s，矛盾。

于是这就证明了 $A_1\cong {\mathbb{Z}}_3$，从而 $\text{Aut}\left(\Gamma \right)=X$。

基金项目

云南省科技厅应用基础研究项目(2019FD116)资助。