3度非弧传递无核Cayley图

Core-Free Nonsymmetric Cayley Graphs of Valency 3

摘要: 设Γ=Cay(G,S)是群G上的Cayley图。称Γ为无核的，如果G在X中是无核的，其中G≤X≤AutΓ。用H表示1∈VΓ在X中的点稳定子。本文对H=16时，度数为3的非弧传递图Γ进行分类研究。

Abstract: Let Γ=Cay(G,S) be a Cayley graph of group G. Then Γ is said to be core-free if G is core-free in X, where G≤X≤AutΓ. Let H be the stabilizer of 1∈VΓ in X. We classify the 3-valent nonsymmetric Cayley graphs where H=16 in this paper.

1. 引言

本文仅讨论有限，简单，连通，无向图。

设 $\Gamma$ 是一个图，其顶点集，边集，弧集，图的全自同构群分别记为 $V\Gamma$， $E\Gamma$， $Arc\Gamma$， $Aut\Gamma$。设 $X\le Aut\left(\Gamma \right)$，我们称图 $\Gamma$ 为X-点传递的，X-边传递的，X-弧传递的，如果X传递地作用在 $V\Gamma$， $E\Gamma$， $Arc\Gamma$。相应地，称图 $\Gamma$ 是点传递的，边传递的，弧传递的，如果 $X=Aut\left(\Gamma \right)$。

设G是一个有限群并记其单位元为1。取 $S\subseteq G-\left\{1\right\}$，称它为G的Cayley子集。设S满足 $S=S^{-1}:=\left\{s^{-1}|s\in S\right\}$。定义群G关于S的Cayley无向图 $\Gamma :=Cay\left(G,S\right)$，其中：

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

我们称Cayley图 $\Gamma =Cay\left(G,S\right)$ 关于G是正规的，如果 $G⊲Aut\Gamma$。记 $Aut\left(G,S\right)=\left\{\alpha \in Aut\left(G\right)|S^{\alpha }=S\right\}$，记 $A_1$ 是顶点1的点稳定子群。由文献 [1] (命题4.22)，我们有， $N_{Aut\Gamma }\left(G\right)=G:Aut\left(G,S\right)$。所以， $\Gamma$ 是正规Cayley图当且仅当 $A_1=Aut\left(G,S\right)$，当且仅当 $Aut\Gamma =G:Aut\left(G,S\right)$。由此可见，正规Cayley图的全自同构群可被原群完全决定。

单群上的Cayley图，对于非弧传递图，目前相关的结论还是非常少。本文尝试做一些研究。

2. 预备知识

设X是任意有限群，H为G的无核子群。设D是H的双陪集的并，满足 $D^{-1}=D$。定义陪集图 $\mathrm{Cos}\left(X,H,D\right)$，其顶点集 $\left[X:H\right]:=\left\{Hx|x\in X\right\}$ 使得 $Hx$ 与 $Hy$ 相邻当且仅当 $y{x}^{-1}\in HDH$。考虑X依右乘作用在H的右陪集集合 $\left[X:H\right]$ 上。注意到该作用是忠实的且保持陪集图的邻接关系，我们可以将X看作图 $\mathrm{Cos}\left(X,H,D\right)$ 的全自同构群 $Aut\left(\mathrm{Cos}\left(X,H,D\right)\right)$ 的一个子群。显然， $\mathrm{Cos}\left(X,H,D\right)$ 是连通的当且仅当 $\langle D\rangle =X$。 $\mathrm{Cos}\left(X,H,D\right)$ 的度数为 $\left|D:H\right|$。容易验证H有n个轨道当且仅当D是n个H的双陪集的并。进一步，下面是关于陪集图性质的熟知的引理，其证明可参考文献 [2] [3] [4]。

引理2.1.设 $\mathrm{Cos}\left(X,H,D\right)$ 的定义如上，则

(1) 若 $\mathrm{Cos}\left(X,H,D\right)$ 是X-对称图，其度数至少为3，则存在元素 $g\in X-H$ 使得 $g^2\in H$， $\langle H,g\rangle =X$。更进一步，我们选择g为一个2-元素。

(2) 设 $\Gamma =Cay\left(G,S\right)$ 是Cayley图且有 $G\le X\le Aut\left(\Gamma \right)$。设 $H=X_{\alpha }$ 是 $\alpha \in V\Gamma$ 在X中的点稳定子，我们有 $\Gamma \cong \mathrm{Cos}\left(X,H,HSH\right)$。

(3) 相反地，设 $\mathrm{Cos}\left(X,H,D\right)$ 是陪集图，G是H在X中的补。记 $S=G\cap D$。则Cayley图 $\Gamma =Cay\left(G,S\right)$ 同构于 $\mathrm{Cos}\left(X,H,D\right)$，因此 $\left|S\right|=\left|D:H\right|$。特别地，如果 $\Gamma$ 的度数为奇数，S包含G的对合。

设 $N=Cor{e}_X\left(G\right)$ 是G在X中的核。由文献 [2]，我们容易得出下列结论。

引理2.2. 设 $\Gamma =Cay\left(G,S\right)$ 是3度Cayley图， $G\le X\le Aut\left(\Gamma \right)$。令 $N=Cor{e}_X\left(G\right)$。用 $X_1$ 表示 $1\in V\Gamma$ 在X中的点稳定子。则下列之一成立：

(1) 若 $G=N$，则 $X\le G:Aut\left(G,S\right)$ 且 $X_1\le Aut\left(G,S\right)$。

(2) 若 $\left|G:N\right|=2$，则存在 $D\subseteq N$，其中 $1\in D$， $\langle D\rangle =N$ 且 $\Gamma \cong BiCay\left(N,D\right)$。

(3) 若 $\left|G:N\right|>2$，N在 $V\Gamma$ 上至少有3个轨道，则 ${\Gamma }_N$ 是关于 $G/N$ 的Cayley图并且是无核的。

注2.2. (a) 若我们限制一些条件，上述引理中有些情形将不会成立。例如，当G是非交换单群时，(2)不会出现。

(b) 在情形(3)中，若 $N=1$，则通过考虑X在 $\left[X:G\right]$ (G在X中右陪集的集合)上的右乘作用，我们可将X视为对称群 $S_n\left(n=\left|X:G\right|\right)$ 的子群，X包含 $S_n$ 的一个同构于H (X作用 $V\Gamma$ 上的一个点稳定子群)的正则子群；对 $\left[X:G\right]$ 中的陪集重新标号为 $1,2,\cdots ,n$，则G为X作用在 $\left\{1,2,\cdots ,n\right\}$ 上的一个点稳定子。

引理2.3. 设 $\Gamma =Cay\left(G,S\right)$ 是连通无核3度非对称Cayley图，其中 $G\le X\le Aut\left(\Gamma \right)$。设H是 $1\in V\Gamma$ 的点稳定子。则存在一个对合 $x_1\in N_X\left(H\right)$ 和2-元素 $x_2\in N_X\left(H\cap H^{x_2}\right)$， $x_1$ 和 $x_2$ 不全包含于 $U_{1\ne K⊲H}{N}_X\left(K\right)$，使得 $\Gamma \cong \mathrm{Cos}\left(X,H,H{x}_{1}H\cup H{x}_{2}H\right)$ 且 $S=G\cap \left(H{x}_{1}H\cup H{x}_{2}H\right)$。

3. 主要结论

设 $\Gamma =Cay\left(G,S\right)$ 是无核(关于G) 3度非弧传递Cayley图，其中 $G\le X\le Aut\left(\Gamma \right)$。用H表示 $1\in V\Gamma$ 在X中的点稳定子。注意到 $\Gamma$ 是3度非弧传递的，可知H一定是2-群，则有下面的结论：

定理3.1. 设 $\left|H\right|=16$。则下列之一成立：

(1) H同构于 $Z_2\times D_8$ ；

(2) H同构于 $Z_2\times Q_8$ ；

(3) 不存在无核3度非弧传递Cayley图。

设 $\Gamma =Cay\left(G,S\right)$ 是无核(关于G) 3度非弧传递Cayley图，其中 $G\le X\le Aut\left(\Gamma \right)$， $H=X_1$ 表示 $1\in V\Gamma$ 在X中的点稳定子。设 $D=H{x}_{1}H\cup H{x}_{2}H$， $P=H\cap H^{x_2}$。由引理2.3，我们有 $\Gamma \cong \mathrm{Cos}\left(X,H,D\right)$，其中对合 $x_1\in N_X\left(H\right)$，2-元素 $x_2\in N_X\left(P\right)$， $x_1$ 和 $x_2$ 不全包含于 $U_{1\ne K⊲H}{N}_X\left(K\right)$。更进一步有 $\langle x_1,x_2,H\rangle =X$ 且 $S=G\cap D$。则P在H中的指数为2。

证明：注意到 $\left|H\right|=16$，由MAGMA [5] 和GAP [6] 可知，对于H，存在14种可能的情形，也就是， $H\cong Z_{16}$, $Z_4\times Z_4$， $\left(Z_4\times Z_2\right):Z_2$， $Z_4:Z_4$， $Z_8\times Z_2$， $Z_8:Z_2$， $D_{16}$， $Q{D}_{16}$， $Q_{16}$， $Z_4\times Z_2\times Z_2$， $Z_2\times D_8$， $Z_2\times Q_8$， $\left(Z_4\times Z_2\right):Z_2$ 或 $Z_2\times Z_2\times Z_2\times Z_2$。我们将对它们一一进行分析。

首先，令 $\Omega :=\left\{1,2,3,\cdots ,16\right\}$。由前段分析，X同构于对称群 $S_{16}$ 的一个子群。假设 $H\cong Z_{16}$，则 $P\cong Z_8$。因为 $\Gamma$ 是3度图， $\left|H:P\right|=2$，注意到循环群的所有子群均为全不变子群，于是 $PcharH$。由于 $x_1\in N_X\left(H\right)$ 且 $x_2\in N_X\left(P\right)$，则 $P^{x_1}=P$。因此， $P⊲\langle x_1,x_2,H\rangle =X$，换句话说，不存在无核3度非弧传递Cayley图。

假设 $H\cong Z_4\times Z_4$，则 $P\cong Z_4\times Z_2$。注意到H和P均只有一个同构于 $Z_2\times Z_2$ 的4阶子群，记为K，则K是H和P的特征子群。又因为 $x_1\in N_X\left(H\right)$， $x_2\in N_X\left(P\right)$，这意味着 $K^{x_1}=K$， $K^{x_2}=K$，所以 $K⊲\langle x_1,x_2,H\rangle =X$，矛盾于H在X中无核。

假设 $H\cong \left(Z_4\times Z_2\right):Z_2$，则 $P\cong Z_4\times Z_2$ 或 $Z_2\times Z_2\times Z_2$。若 $P\cong Z_2\times Z_2\times Z_2$，因为 $H^{x_1}=H$ 且P是H中唯一同构于 $Z_2\times Z_2\times Z_2$ 的子群，这意味着 $P^{x_1}=P$。另一方面，由于 $P^{x_2}=P$， $P⊲H$，我们有 $P⊲\langle x_1,x_2,H\rangle =X$，矛盾。若 $P\cong Z_4\times Z_2$，由MAGMA和GAP可知，不存在满足条件的 $x_2$ 使得 $\Gamma$ 是无核(关于G) 3度非弧传递Cayley图。

假设 $H\cong Z_4:Z_4$，则 $P\cong Z_4\times Z_2$。同样地，与 $H\cong Z_4\times Z_4$ 的情形有相同的讨论，推出矛盾。

假设 $H\cong Z_8\times Z_2$，则 $P\cong Z_4\times Z_2$ 或 $Z_8$。先假设前者成立，也即， $P\cong Z_4\times Z_2$。因为 $H^{x_1}=H$ 且P是H中唯一同构于 $Z_4\times Z_2$ 的子群，这意味着 $P^{x_1}=P$。另一方面，由于 $P^{x_2}=P$， $P⊲H$，我们有 $P⊲\langle x_1,x_2,H\rangle =X$，矛盾。现设 $H=\langle a\rangle \times \langle b\rangle \cong Z_8\times Z_2$， $P=\langle a\rangle \cong Z_8$，其中 $a=\left(11241021139\right)\left(516814615713\right)$， $b=\left(15\right)\left(26\right)\left(37\right)\left(48\right)\left(913\right)\left(1014\right)\left(1115\right)\left(1216\right)$。注意到P中只有一个4阶子群同构于 $Z_4$，也即， $\langle a^2\rangle$，则 $\langle a^2\rangle char\langle a\rangle =P⊲H$，于是 $\langle a^2\rangle ⊲H$。因为 $x_2\in N_X\left(P\right)$，我们有 ${\langle a^2\rangle }^{x_2}=\langle a^2\rangle$。因为H中有两个8阶子群同构于 $Z_8$，也即， $\langle a\rangle$ 和 $\langle ab\rangle$，因为 $x_1\in N_X\left(H\right)$，那么 ${\langle a\rangle }^{x_1}=\langle a\rangle$ 或 $\langle ab\rangle$。若 $P^{x_1}={\langle a\rangle }^{x_1}=\langle a\rangle =P$，又 $x_2\in N_X\left(P\right)$，推出 $P⊲\langle x_1,x_2,H\rangle =X$，矛盾。注意到H中有两个4阶子群同构于 $Z_4$，也即， $\langle a^2\rangle$ 和 $\langle a^{2}b\rangle$，因为 $x_1\in N_X\left(H\right)$,那么 ${\langle a^2\rangle }^{x_1}=\langle a^2\rangle$ 或 $\langle a^{2}b\rangle$。若 ${\langle a\rangle }^{x_1}=\langle ab\rangle$，注意到 $a^2={\left(ab\right)}^2=\left(1423\right)\left(5867\right)\left(9121011\right)\left(13161415\right)$，我们有 ${\langle a^2\rangle }^{x_1}=\langle {\left(ab\right)}^2\rangle =\langle a^2\rangle$。因此 $\langle a^2\rangle ⊲\langle x_1,x_2,H\rangle =X$，这与H在X中无核矛盾。

假设 $H\cong Z_8:Z_2$，则 $P\cong Z_4\times Z_2$ 或 $Z_8$。同样地，与 $H\cong Z_8\times Z_2$ 的情形相同的讨论，推出矛盾。

假设 $H\cong D_{16}$，则 $P\cong D_8$ 或 $Z_8$。注意到H中只有一个同构于 $Z_4$ 的4阶子群。由MAGMA和GAP， $D_8$ 和 $Z_8$ 均是只有一个同构于 $Z_4$ 的4阶子群，令 $K\cong Z_4$。所以K是H和P的特征子群。由于 $x_1$ 和 $x_2$ 的选择， $K⊲\langle x_1,x_2,H\rangle =X$，矛盾。

假设 $H\cong Q{D}_{16}$，则 $P\cong Q_8$， $Z_8$ 或 $D_8$。注意到H中分别只有一个同构于 $Q_8$， $Z_8$ 和 $D_8$ 的8阶子群。所以当P为以上三种子群中的任何一种时，我们有 $PcharH$。另一方面，由于 $x_1\in N_X\left(H\right)$， $x_2\in N_X\left(P\right)$，则有 $P^{x_1}=P$，因此我们推出 $P⊲\langle x_1,x_2,H\rangle =X$，矛盾。

假设 $H\cong Q_{16}$，则 $P\cong Q_8$ 或 $Z_8$。注意到H中只有一个2阶子群同构于 $Z_2$。由MAGMA和GAP， $Q_8$ 和 $Z_8$ 均是只有一个同构于 $Z_2$ 的子群，令 $K\cong Z_2$。所以K是H和P的特征子群。从而必有 $K⊲X$，矛盾。

假设 $H\cong Z_4\times Z_2\times Z_2$，则 $P\cong Z_4\times Z_2$ 或 $Z_2\times Z_2\times Z_2$。若 $P\cong Z_2\times Z_2\times Z_2$，因为 $H^{x_1}=H$ 且P为H中唯一同构于 $Z_2\times Z_2\times Z_2$ 的子群，这意味着 $P^{x_1}=P$。另一方面，由于 $P^{x_2}=P$， $P⊲H$，于是 $P⊲\langle x_1,x_2,H\rangle =X$，矛盾。若 $P\cong Z_4\times Z_2$，由MAGMA和GAP可知，不存在满足条件的 $x_2$ 使得 $\Gamma$ 是无核(关于G) 3度非弧传递Cayley图。

假设 $H\cong \left(Z_4\times Z_2\right):Z_2$，则 $P\cong D_8$， $Q_8$ 或 $Z_4\times Z_2$。由MAGMA和GAP可知，不存在满足条件的 $x_2$ 使得 $\Gamma$ 是无核(关于G) 3度非弧传递Cayley图。

假设 $H\cong Z_2\times Z_2\times Z_2\times Z_2$，则 $P\cong Z_2\times Z_2\times Z_2$。设 $H=\langle a,b,c,d\rangle$，其中

$b=\left(15\right)\left(26\right)\left(37\right)\left(48\right)\left(913\right)\left(1014\right)\left(1115\right)\left(1216\right)$,

$c=\left(13\right)\left(24\right)\left(57\right)\left(68\right)\left(911\right)\left(1012\right)\left(1315\right)\left(1416\right)$,

$d=\left(12\right)\left(34\right)\left(56\right)\left(78\right)\left(910\right)\left(1112\right)\left(1314\right)\left(1516\right)$.

我们断言a是由b，c和d决定的。设 $P=\langle b,c,d\rangle$。显然P在 $\Omega$ 上半正则，且有两个轨道，记为 ${\Delta }_1=\left\{1,2,3,4,5,6,7,8\right\}$， ${\Delta }_2=\left\{9,10,11,12,13,14,15,16\right\}$。因为H在 $\Omega$ 上是正则的，则 ${\Delta }_1^a={\Delta }_2$。可以发现 ${\Sigma }_1=\left\{1,5\right\}$， ${\Sigma }_2=\left\{2,6\right\}$， ${\Sigma }_3=\left\{3,7\right\}$， ${\Sigma }_4=\left\{4,8\right\}$， ${\Sigma }_5=\left\{9,13\right\}$， ${\Sigma }_6=\left\{10,14\right\}$， ${\Sigma }_7=\left\{11,15\right\}$， ${\Sigma }_8=\left\{12,16\right\}$ 是b在 $\Omega$ 上的8个轨道； ${{\Sigma }^{\prime }}_1=\left\{1,3\right\}$， ${{\Sigma }^{\prime }}_2=\left\{2,4\right\}$， ${{\Sigma }^{\prime }}_3=\left\{5,7\right\}$， ${{\Sigma }^{\prime }}_4=\left\{6,8\right\}$， ${{\Sigma }^{\prime }}_5=\left\{9,11\right\}$， ${{\Sigma }^{\prime }}_6=\left\{10,12\right\}$， ${{\Sigma }^{\prime }}_7=\left\{13,15\right\}$， ${{\Sigma }^{\prime }}_8=\left\{14,16\right\}$ 是c在 $\Omega$ 上的8个轨道； ${{\Sigma }^{″}}_1=\left\{1,2\right\}$， ${{\Sigma }^{″}}_2=\left\{3,4\right\}$， ${{\Sigma }^{″}}_3=\left\{5,6\right\}$， ${{\Sigma }^{″}}_4=\left\{7,8\right\}$， ${{\Sigma }^{″}}_5=\left\{9,10\right\}$， ${{\Sigma }^{″}}_6=\left\{11,12\right\}$， ${{\Sigma }^{″}}_7=\left\{13,14\right\}$， ${{\Sigma }^{″}}_8=\left\{15,16\right\}$ 是d在 $\Omega$ 上的8个轨道。回忆到 ${\Delta }_1^a={\Delta }_2$，我们有 ${\left({\Sigma }_i\right)}^a={\Sigma }_j$， ${\left({{\Sigma }^{\prime }}_i\right)}^a={{\Sigma }^{\prime }}_j$， ${\left({{\Sigma }^{″}}_i\right)}^a={{\Sigma }^{″}}_j$，其中 $i=1,2,3,4$， $j=5,6,7,8$。通过计算可知，a的所有可能的情况有8种，将其记为集合M，

$\begin{array}{c}M=\{\left(19\right)\left(513\right)\left(311\right)\left(210\right)\left(614\right)\left(412\right)\left(715\right)\left(816\right),\\ \left(110\right)\left(514\right)\left(312\right)\left(211\right)\left(615\right)\left(413\right)\left(716\right)\left(89\right),\\ \left(111\right)\left(515\right)\left(313\right)\left(212\right)\left(616\right)\left(414\right)\left(79\right)\left(810\right),\\ \left(112\right)\left(516\right)\left(314\right)\left(213\right)\left(69\right)\left(415\right)\left(710\right)\left(811\right),\\ \left(113\right)\left(59\right)\left(315\right)\left(214\right)\left(610\right)\left(416\right)\left(711\right)\left(812\right),\\ \left(114\right)\left(510\right)\left(316\right)\left(29\right)\left(613\right)\left(411\right)\left(712\right)\left(815\right),\\ \left(115\right)\left(511\right)\left(39\right)\left(216\right)\left(612\right)\left(410\right)\left(713\right)\left(814\right),\\ \left(116\right)\left(512\right)\left(310\right)\left(215\right)\left(611\right)\left(49\right)\left(714\right)\left(813\right)\}\end{array}$

因为H在 $\Omega$ 上正则且 $x_2\in N_X\left(P\right)$， $H^{x_2}=\langle P,a^{x_2}\rangle$ 在 $\Omega$ 也是正则的，由上面的叙述可知 $a^{x_2}\in M$,从而 $M^{x_2}=M$。不失一般性，设 $a=\left(19\right)\left(513\right)\left(311\right)\left(210\right)\left(614\right)\left(412\right)\left(715\right)\left(816\right)$，将其余元素分别记为 $n_1,n_2,n_3,n_4,n_5,n_6,n_7$。因此 $M=\left\{a,n_1,n_2,n_3,n_4,n_5,n_6,n_7\right\}$。然而，通过计算， $\langle n_1,b,c,d\rangle \cong \left(\left(Z_4\times Z_4\right):Z_2\right):Z_2$， $\langle n_2,b,c,d\rangle \cong Z_2\times D_8$， $\langle n_3,b,c,d\rangle \cong \left(\left(Z_4\times Z_4\right):Z_2\right):Z_2$， $\langle n_5,b,c,d\rangle \cong Z_2\times D_8$， $\langle n_6,b,c,d\rangle \cong Z_2\times D_8$， $\langle n_7,b,c,d\rangle \cong Z_2\times D_8$， $\langle n_4,b,c,d\rangle \cong Z_2\times Z_2\times Z_2\times Z_2\cong \langle a,b,c,d\rangle$。所以只有a和 $n_4$ 满足条件。注意到 $n_4=ab$，则 $H^{x_2}=\langle P,a^{x_2}\rangle =\langle P,a\rangle$ 或 $\langle P,ab\rangle =\langle a,b,c,d\rangle$，从而 $H⊲X$，这矛盾于H在X中是无核的。即完成了定理3.1的证明。

基金项目

国家自然科学基金项目(12061089，11701503)；云南省科技厅面上项目(2018FB003)。

NOTES

^*通讯作者。