云南民族大学数学与计算机科学学院，云南 昆明

收稿日期：2023年7月1日；录用日期：2023年7月23日；发布日期：2023年8月1日

摘要

在具有较高对称性的图中，正则Cayley图是一类特殊的对称图。称一个图 $\Gamma$ 为2-正则图，如果 $\Gamma$ 的全自同构群 $Aut\Gamma$ 作用在2-弧集上正则。本文给出了点稳定子为F₂₀的5度无核2-正则Cayley图的部分分类。

关键词

无核，2-正则，Cayley图

Core-Free Pentavalent 2-Regular Cayley Graphs with Vertex Stabilizer F₂₀

Xin Ru^*, Luqing Zhao

School of Mathematics and Computer Sciences, Yunnan Minzu University, Kunming Yunnan

Received: Jul. 1^st, 2023; accepted: Jul. 23^rd, 2023; published: Aug. 1^st, 2023

ABSTRACT

Among graphs with higher symmetry, regular Cayley graphs are a special class of symmetric graphs. A graph $\Gamma$ is called 2-regular if its full automorphism group $Aut\Gamma$ acts regularly on its 2-arcs. In this paper, it is given that a partial classification of core-free pentavalent 2-regular Cayley graphs with the vertex stabilizer F₂₀.

Keywords:Core-Free, 2-Regular, Cayley Graph

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

为方便研究，本文假设所有的图都是有限、简单、连通和无向的。

设 $\Gamma$ 是一个图， $V\Gamma$ 、 $E\Gamma$ 、 $\text{Arc}\Gamma$ 和 $\text{Aut}\Gamma$ 分别代表图的顶点集、边集、弧集和全自同构群， $\text{val}\Gamma$ 表示图 $\Gamma$ 的度数。

设 $X\le \text{Aut}\Gamma$ ，s是一个正整数。一个图 $\Gamma$ 被称为是 $\left(X,s\right)$ -弧传递的，如果X传递作用在 $\Gamma$ 的s-弧集上，其中，s-弧是一个由 $s+1$ 个顶点组成的 $\left(s+1\right)$ -数组，且对于 $\forall i,v_{i-1}\ne v_{i+1}$ ，满足 $\left(v_{i-1},v_i\right)\in E\Gamma$ 。称图 $\Gamma$ 为s-弧正则图，如果它的全自同构群在其弧集上是正则的。

设G是有限群，其单位元素是1，一个图 $\Gamma$ 被称为G的一个Cayley图，如果在G中有一个子集S，满足 $1\notin S$ ，且 $S=S^{-1}$ ，使得

$V\Gamma =G,E\Gamma =\left\{\left(s,sg\right)|g\in G,s\in S\right\},$

其中 $S^{-1}=\left\{s^{-1}|s\in S\right\}$ 。我们用 $\text{Cay}\left(G,S\right)$ 表示Cayley图 $\Gamma$ ，Cayley图 $\Gamma$ 的度数为 $\left|S\right|$ ，另外，G可以被看作 $\text{Aut}\Gamma$ 的一个正则子群，其中G右乘作用在 $V\Gamma$ 上。为了方便，我们仍然用G代表这个正则子群，则Cayley图是点传递的；相反，一个点传递图 $\Gamma$ 是群G的一个Cayley图，当且仅当 $\text{Aut}\Gamma$ 包含同构于G的一个正则子群。一个Cayley图 $\text{Cay}\left(G,S\right)$ 被称为G的一个正规Cayley图，如果G是 $\text{Aut}\left(\text{Cay}\left(G,S\right)\right)$ 的一个正规子群；称 $\text{Cay}\left(G,S\right)$ 是无核的，如果G在某些 $X\le \text{Aut}\left(\text{Cay}\left(G,S\right)\right)$ 中是无核的，即 ${\text{Core}}_X\left(G\right):={\displaystyle {\cap }_{x\in X}{G}^X}=1$ 。

正则Cayley图是一类对称性较高的点传递图，代数图论中对这类图的研究一直是一个热门问题。图论学者最初从3度1-正则图开始研究，R.Frucht在文献 [1] 中构造出第一个3度1-正则图的例子；Li和Lou等在文献 [2] 中证明了如果一个5度的 $\left(X,1\right)$ -正则Cayley图不是正规的或双正规的；Ling和Lou在文献 [3] 中给出了连通无核5度1-传递Cayley图的特征和分类；Li和Lou在文献 [4] 中给出了7度无核1-正则Cayley图的一个分类；奇素数度的1-正则Cayley图的完全分类及其相关结论可参见文献 [5] ；另外，关于5度图的更多性质和分类结果可参见文献 [6] [7] [8] [9] [10] 。

本文主要针对点稳定子为F₂₀的5度无核2-正则Cayley图进行研究和分类，考虑前10种共轭类的情况，得到以下主要结果：

定理1.1 设 $\Gamma =\text{Cay}\left(G,S\right)$ 是无核5度2-正则Cayley图， ${\left(\text{Aut}\Gamma \right)}_1$ 是1在 $\text{Aut}\Gamma$ 中的稳定子，且同构于F₂₀，则下列之一成立：

1) $\Gamma$ 同构于表1中的一个图；

2) 存在一个 $\text{Aut}\Gamma$ 的子群X，使得 $G\le X$ ，且G在X中无核。进一步，G和X的描述见表2。

表1. 点稳定子为F₂₀的5度无核2-正则Cayley图

表2. 点稳定子为F₂₀的5度无核2-正则Cayley图的候选

2. 预备知识

设X是有限群，H是X的无核子群，对于一个元素 $g\in X-H$ ，定义图 $\Gamma =\mathrm{Cos}\left(X,H,g\right)$ ，顶点集 $\left[X:H\right]$ 是H在X中的右陪集，使得Hx和Hy相邻当且仅当 $y{x}^{-1}\in HgH$ ，则 $X\le \text{Aut}\Gamma$ 在它的弧集上传递，其中X右乘作用在 $\left[X:H\right]$ 上，这样的图叫做陪集图，且 $\Gamma$ 连通当且仅当 $\langle H,g\rangle =X$ ， $\Gamma$ 的度为 $\left|H:H\cap H^g\right|$ 。另外，若有一个正则子群G，则 $\Gamma \cong \text{Cay}\left(G,G\cap HgH\right)$ 。

对于一个无核X-弧传递Cayley图 $\Gamma =\text{Cay}\left(G,S\right)$ ，其中 $G\le X\le \text{Aut}\left(\Gamma \right)$ ，设 $v\in V\Gamma$ ， $H=X_v$ 是v在X中的稳定子群，假设 $\left|H\right|=n$ ，考虑X在 $\left[X:G\right]$ 上的右乘作用，则X是对称群 $S_n$ 的一个子群，在这个作用下，H是 $S_n$ 的一个正则子群，且G是X中 $i\in \left\{1,2,\cdots ,n\right\}$ 的一个稳定子，不失一般性，我们可以假设G稳定1。由(文献 [11] ，命题3.2)，我们有以下结论：

引理2.1 设 $\Gamma =\text{Cay}\left(G,S\right)$ 一个无核X-弧传递Cayley图， $G\le X\le \text{Aut}\left(\Gamma \right)$ ，设 $v\in V\Gamma$ ， $H=X_v$ 是v在X中的稳定子群，假设 $\left|H\right|=n$ ，则X是 $S_n$ 的一个子群，且H正则作用在 $\left\{1,2,\cdots ,n\right\}$ 上。另外，若S包含一个对合 $\tau$ ，则 $\tau \in {\text{N}}_{{\text{S}}_n}\left(H\cap H^{\tau }\right)-\left({\cup }_{1\ne K⊲H}{\text{N}}_{{\text{S}}_n}\left(K\right)\right)$ ， $\Gamma \cong \mathrm{Cos}\left(X,H,\tau \right)$ ， $X=\langle H,\tau \rangle$ ， $G=\left\{\sigma \in X|1^{\sigma }=1\right\}$ ， $S=\left\{\sigma \in H\tau H|1^{\sigma }=1\right\}$ 。

对于连通5度 $\left(X,s\right)$ -传递图，由文献 [12] 和 [13] ，我们有以下引理：

引理2.2 设 $\Gamma$ 是一个5度 $\left(X,s\right)$ -传递图， $X\le \text{Aut}\Gamma$ ，且 $s\ge 1$ ，设 $v\in V\Gamma$ ，F₂₀表示20阶的Frobenius群，则：

1) 如果 $X_v$ 是可解的，则 $\left|X_v\right||80$ ，且 $s\le 3$ ，其中， $\left(X_v,s\right)$ 在表3中；

2) 如果 $X_v$ 是不可解的，则 $\left|X_v\right||2^9\cdot 3^2\cdot 5$ ，且 $2\le s\le 5$ ，其中， $\left(X_v,s\right)$ 在表4中。

表3. 可解的点稳定子

表4. 不可解的点稳定子

3. 主要结论

设 $\Gamma =\text{Cay}\left(G,S\right)$ 是无核5度2-正则Cayley图，则S中一定包含一个对合 $\tau$ ，由引理2.1可知，H是 $S_n$ 的一个正则子群。我们可以假设 $H=\langle a,b\rangle \cong {\text{F}}_{20}$ ，其中 $a=\left(\text{113720}\right)\left(\text{215618}\right)\left(\text{3121016}\right)\left(\text{414919}\right)$ $\left(\text{5 11 8 17}\right)$， $b=\left(\text{115819}\right)\left(\text{212717}\right)\left(\text{314620}\right)\left(\text{4111018}\right)\left(\text{513916}\right)$ 。假设 $P=\langle a\rangle$ ，则 $\text{Cay}\left(G,S\right)\cong \text{Cos}\left(X,H,\tau \right)$ ，其中 $\tau \in {\text{N}}_{{\text{S}}_{20}}\left(P\right)-\left({\cup }_{1\ne K⊲H}{\text{N}}_{{\text{S}}_{20}}\left(K\right)\right)$ ， $X=\langle H,\tau \rangle \le S_{20}$ ， $G=\left\{\sigma \in X|1^{\sigma }=1\right\}$ ， $S=\left\{\sigma \in H\tau H|1^{\sigma }=1\right\}$ 。由Magma (文献 [14] )易计算出 $\tau$ 有846种选择，它们在 ${\text{N}}_{{\text{S}}_{20}}\left(H\right)$ 中被分为159种共轭类。本文仅考虑前10种共轭类，它们的代表元如下：

${\tau }_1=\left(45\right)\left(89\right)\left(1114\right)\left(1719\right),$

${\tau }_2=\left(1117\right)\left(1216\right)\left(1320\right)\left(1419\right)\left(1518\right),$

${\tau }_3=\left(45\right)\left(89\right)\left(1119\right)\left(1216\right)\left(1320\right)\left(1417\right)\left(1518\right),$

${\tau }_4=\left(26\right)\left(310\right)\left(49\right)\left(58\right)\left(1117\right)\left(1216\right)\left(1419\right)\left(1518\right),$

${\tau }_5=\left(23\right)\left(45\right)\left(610\right)\left(89\right)\left(1114\right)\left(1215\right)\left(1618\right)\left(1719\right),$

${\tau }_6=\left(26\right)\left(310\right)\left(49\right)\left(58\right)\left(1320\right),$

${\tau }_7=\left(26\right)\left(310\right)\left(48\right)\left(59\right)\left(1119\right)\left(1216\right)\left(1417\right)\left(1518\right),$

${\tau }_8=\left(215\right)\left(312\right)\left(414\right)\left(511\right)\left(618\right)\left(817\right)\left(919\right)\left(1016\right)\left(1320\right),$

${\tau }_9=\left(215\right)\left(312\right)\left(411\right)\left(514\right)\left(618\right)\left(819\right)\left(917\right)\left(1016\right)\left(1320\right),$

${\tau }_{10}=\left(218\right)\left(316\right)\left(417\right)\left(519\right)\left(615\right)\left(814\right)\left(911\right)\left(1012\right)\left(1320\right).$

现在设 $\Omega =\left\{1,2,\cdots ,20\right\}$ ， $X_j=\langle H,{\tau }_j\rangle$ ， ${\Gamma }_j=\mathrm{Cos}\left(X_j,H,{\tau }_j\right)$ ，其中 $j=1,2,\cdots ,10$ 。设 $G_j=\left\{\sigma \in X_j|1^{\sigma }=1\right\}$ ， $S_j=\left\{\sigma \in H{\tau }_{j}H|1^{\sigma }=1\right\}$ 。注意到，H是 $X_j$ 的一个正则子群， $G_j$ 是 $X_j$ 作用在 $\Omega$ 上的1的点稳定子。由此， $X_j=G_{j}H$ ，且 $G_j\cap H=1$ ，则 $G_j$ 正则作用在 $\left[X_j:H\right]$ 上，进而得 ${\Gamma }_j=\text{Cay}\left(G_j,S_j\right)$ 。本文主要结论如下：

引理3.1 对于 $j=1,2,\cdots ,6$ ，如果 ${\Gamma }_j$ 是2-正则图，则：

1) $j=3$ ， $G_3\cong {\mathbb{Z}}_2^2:{\text{S}}_3$ ， $\text{Aut}{\Gamma }_3\cong {\mathbb{Z}}_2^2:{\text{S}}_5$ ， $S_3=\left\{{\tau }_3,a_3,b_3,b_3^{-1},c_3\right\}$ ，且 ${\Gamma }_3\cong \text{Cay}\left(G_3,S_3\right)$ ；

2) $j=5$ ， $G_5\cong {\text{A}}_4\times {\text{A}}_5$ ， $\text{Aut}{\Gamma }_5\cong \left({\text{A}}_5\times {\text{A}}_5\right):{\mathbb{Z}}_4$ ， $S_5=\left\{{\tau }_5,a_5,a_5^{-1},b_5,b_5^{-1}\right\}$ ，且 ${\Gamma }_5\cong \text{Cay}\left(G_5,S_5\right)$ ；

其中 $a_3=\left(\text{34}\right)\left(\text{78}\right)\left(\text{1120}\right)\left(\text{1219}\right)\left(\text{1316}\right)\left(\text{1417}\right)\left(\text{1518}\right)$ ，

$b_3=\left(\text{2543}\right)\left(\text{6987}\right)\left(\text{11181320}\right)\left(\text{12191516}\right)\left(\text{1417}\right)$ ，

$c_3=\left(\text{23}\right)\left(\text{67}\right)\left(\text{1118}\right)\left(\text{1220}\right)\left(\text{1316}\right)\left(\text{1417}\right)\left(\text{1519}\right)$ ，

$a_5=\left(\text{254}\right)\left(\text{6108}\right)\left(\text{1113141512}\right)\left(\text{1617191820}\right)$ ，

$b_5=\left(\text{253}\right)\left(\text{698}\right)\left(\text{1112131514}\right)\left(\text{1618192017}\right)$ 。

证明：首先，我们可由Magma (文献 [14] )分别计算出 $\text{Aut}{\Gamma }_j$ 和 $G_j$ 的阶以及 $S_j$ 中的元素。

对于一个顶点 $v\in V{\Gamma }_j$ ，由Magma (文献 [14] )计算得， $\left|{\left(\text{Aut}{\Gamma }_1\right)}_v\right|=\left|{\left(\text{Aut}{\Gamma }_6\right)}_v\right|=40$ ， $\left|{\left(\text{Aut}{\Gamma }_2\right)}_v\right|=2880$ ， $\left|{\left(\text{Aut}{\Gamma }_4\right)}_v\right|=120$ ，则由引理2.2，这些图都不是2-正则图。

当 $j=3$ 时，由Magma (文献 [14] )计算可得， $G_3$ 有一个4阶的正规子群是初等交换群 ${\mathbb{Z}}_2^2$ ，且它的补与 $S_3$ 同构； $\text{Aut}{\Gamma }_3$ 存在一个正规子群是初等交换群 ${\mathbb{Z}}_2^2$ ，它的补是一个120阶的非交换群，易验证其与 $S_3$ 同构。所以，我们得 $G_3\cong {\mathbb{Z}}_2^2:{\text{S}}_3$ ， $\text{Aut}{\Gamma }_3\cong {\mathbb{Z}}_2^2:{\text{S}}_5$ 。

当 $j=5$ 时，由Magma (文献 [14] )易得， $G_5$ 的阶为720，它有6个正规子群，其中阶为12的正规子群和阶为60的正规子群的交为1，且这两个正规子群分别同构于 ${\text{A}}_4$ 和 ${\text{A}}_5$ ，从而得 $G_5\cong {\text{A}}_4\times {\text{A}}_5$ 。另外， $\text{Aut}{\Gamma }_5$ 有一个阶为3600的正规子群，它显然同构于 ${\text{A}}_5\times {\text{A}}_5$ ，且它的补是阶为4的交换群，与 ${\mathbb{Z}}_4$ 同构，因此 $\text{Aut}{\Gamma }_5\cong \left({\text{A}}_5\times {\text{A}}_5\right):{\mathbb{Z}}_4$ ，引理得证。

引理3.2 $G_7\cong {\text{A}}_9:{\text{S}}_{10}$ ， $X_7\cong \left({\text{A}}_{10}\times {\text{A}}_{10}\right):{\mathbb{Z}}_4$ ，且 $S_7=\left\{{\tau }_7,a_7,b_7,b_7^{-1},c_7\right\}$ ，其中

$a_7=\left(34\right)\left(56\right)\left(78\right)\left(1219\right)\left(1315\right)\left(1618\right)$ ， $b_7=\left(25438769\right)\left(1112\right)\left(131516181714\right)\left(1920\right)$ ，

$c_7=\left(23\right)\left(410\right)\left(67\right)\left(1118\right)\left(1214\right)\left(1720\right)$ 。

证明：假设 $j=7$ ，由Magma (文献 [14] )可以直接计算出Cayley子集 $S_7$ 中的元素，且 $G_7$ 有一个同构于 ${\text{A}}_9$ 的正规子群，它在 $G_7$ 中的补同构于 $S_{10}$ ，进而我们得 $G_7\cong {\text{A}}_9:{\text{S}}_{10}$ 。

另外，由于 $X_7=\langle a,b,{\tau }_7\rangle$ ，我们由Magma (文献 [14] )可以计算出 $X_7$ 的正规子群有4个，其中一个正规子群的阶为3292047360000，易验证它是 ${\text{A}}_{10}$ 和 ${\text{A}}_{10}$ 的直积，进一步地，我们得到它的补与 ${\mathbb{Z}}_4$ 同构，最终我们有 $X_7\cong \left({\text{A}}_{10}\times {\text{A}}_{10}\right):{\mathbb{Z}}_4$ ，引理得证。

引理3.3 $G_8\cong {\mathbb{Z}}_2^9:{\text{S}}_9$ ， $X_8\cong {\mathbb{Z}}_2^{10}:{\text{S}}_{10}$ ，且 $S_8=\left\{{\tau }_8,a_8,b_8,c_8,d_8\right\}$ ，其中

$a_8=\left(519\right)\left(612\right)\left(1120\right)\left(1318\right)\left(1417\right)\left(1516\right)$ ， $b_8=\left(317\right)\left(915\right)\left(1116\right)\left(1220\right)\left(1319\right)\left(1418\right)$ ，

$c_8=\left(216\right)\left(814\right)\left(1119\right)\left(1218\right)\left(1317\right)\left(1520\right)$ ， $d_8=\left(418\right)\left(1011\right)\left(1217\right)\left(1316\right)\left(1420\right)\left(1519\right)$ 。

证明：假设 $j=8$ ，由Magma (文献 [14] )，我们可以直接计算出Cayley子集 $S_8$ 中的元素，且 $G_8$ 有一个阶为512的正规子群是初等交换群，即 ${\mathbb{Z}}_2^9$ ，它在 $G_8$ 中的补的阶为362880，易验证其与 $S_9$ 同构，从而得 $G_8\cong {\mathbb{Z}}_2^9:{\text{S}}_9$ 。

进一步地，因 $X_8=\langle a,b,{\tau }_8\rangle$ ，我们可得 $X_8$ 有9个正规子群，由Magma (文献 [14] )验证其中一个阶为1024的正规子群是初等交换群 ${\mathbb{Z}}_2^{10}$ ，它的补同构于 ${\text{S}}_{10}$ ，从而得 $X_8\cong {\mathbb{Z}}_2^{10}:{\text{S}}_{10}$ ，引理得证。

引理3.4 $G_9\cong G_{10}\cong {\text{A}}_{19}:{\mathbb{Z}}_2$ ， $X_9\cong X_{10}\cong {\text{A}}_{20}:{\mathbb{Z}}_2$ ，且 $S_9=\left\{{\tau }_9,a_9,b_9,b_9^{-1},c_9\right\}$ ， $S_{10}=\left\{{\tau }_{10},a_{10},b_{10},b_{10}^{-1},c_{10}\right\}$ ，其中 $a_9=\left(34\right)\left(519\right)\left(612\right)\left(78\right)\left(1120\right)\left(1316\right)\left(1417\right)\left(1518\right)$ ，

$b_9=\left(25431612191587691417\right)\left(11181320\right)$ ，

$c_9=\left(23\right)\left(418\right)\left(67\right)\left(1011\right)\left(1220\right)\left(1316\right)\left(1417\right)\left(1519\right)$ ，

$a_{10}=\left(34\right)\left(512\right)\left(619\right)\left(78\right)\left(1120\right)\left(1316\right)\left(1417\right)\left(1518\right)$ ，

$b_{10}=\left(25431417876916121915\right)\left(11181320\right)$ ，

$c_{10}=\left(23\right)\left(411\right)\left(67\right)\left(1018\right)\left(1220\right)\left(1316\right)\left(1417\right)\left(1519\right)$ 。

证明：首先，我们可以由Magma (文献 [14] )直接计算出Cayley子集 $S_9$ 和 $S_{10}$ 中的元素。

假设 $j=9$ ，由Magma (文献 [14] )，我们可以得到 $G_9$ 的3个正规子群，易验证 $G_9$ 的非单位真正规子群是单群，且与 ${\text{A}}_{19}$ 同构，它在 $G_9$ 中的补同构于 ${\mathbb{Z}}_2$ ，因此 $G_9\cong {\text{A}}_{19}:{\mathbb{Z}}_2$ 。

另外，因 $X_9=\langle a,b,{\tau }_9\rangle$ ，我们可由Magma (文献 [14] )计算出 $X_9$ 的阶和正规子群，从而得到 $X_9$ 的非单位真正规子群同构于 ${\text{A}}_{20}$ ，它的补与 ${\mathbb{Z}}_2$ 同构，因此 $X_9\cong {\text{A}}_{20}:{\mathbb{Z}}_2$ 。

进一步，由Magma (文献 [14] )，我们有 $G_9\cong G_{10}$ ，且 $X_9\cong X_{10}$ ，引理得证。

对于点稳定子为F₂₀的无核5度2-正则Cayley图 $\Gamma$ ，其Cayley子集S中包含的对合 $\tau$ 在 ${\text{N}}_{{\text{S}}_{20}}\left(H\right)$ 中共有159种共轭类，本文在定理1.1中仅描述前10种共轭类的情况。综合引理3.1、引理3.2、引理3.3和引理3.4的证明，定理1.1得证。

文章引用

茹 昕,赵路清. 点稳定子为F₂₀的5度无核2-正则Cayley图
Core-Free Pentavalent 2-Regular Cayley Graphs with Vertex Stabilizer F₂₀[J]. 应用数学进展, 2023, 12(08): 3495-3500. https://doi.org/10.12677/AAM.2022.128347

参考文献