关于小阶数非交换群的简化幂图

On the Reduced Power Graphs of Non-Abelian Groups of Small Order

摘要: 给定一个有限群G，群G上的简化幂图是以G的所有元素为顶点集合的一个简单图，其中两个不同的顶点x和y相邻当且仅当⊂或⊂。本文将给出14阶以内的非交换群的简化幂图的结构。此外本文也求了这些群简化幂图的独立数、团数以及彩虹连通数。

Abstract: Given a finite group G, the reduced power graph of G is an undirected graph with vertex set G, and two distinct vertices x and y are adjacent if and only if ⊂ or⊂. This paper characterizes the structures of the reduced power graphs of non-abelian groups of order at most 14. Moreover, this paper also computes the independence number, clique number, and the rainbow connection number of these graphs.

1. 引言

本文所涉及的任一图均为一个简单图，即没有重边和自环的无向图。设 $\Gamma$ 是一个图， $\Gamma$ 的顶点集和边集分别用 $V\left(\Gamma \right)$ 和 $E\left(\Gamma \right)$ 表示。如果 $V\left(\Gamma \right)$ 的一个子集U中任意两个顶点在 $\Gamma$ 中都不能相连，则称U为 $\Gamma$ 的一个独立集。如果向某个独立集中添加任一个在该独立集之外的顶点之后，新构成的集合不再是 $\Gamma$ 的独立集，则原独立集称为是图 $\Gamma$ 的一个极大独立集。具有最大基数的独立集的基数称为图 $\Gamma$ 的独立数。如果 $V\left(\Gamma \right)$ 的一个子集C中任意两个顶点在 $\Gamma$ 中都相连，则称C为 $\Gamma$ 的一团。具有最大基数的团的大小称为 $\Gamma$ 的团数。

群上的凯莱图有非常悠久的研究历史，环上的零因子图是近二十年来的一个研究热门课题。研究群或某个代数系统上的图是近些年来的一个新的研究方向。一方面可以根据图的一些性质决定群或代数系统的结构，另一方面，研究这些图在自动化理论的应用。到目前为止，结合图跟环或群然后研究这些图的论文已经不胜枚举，除了前面提到的凯莱图与零因子图以外，如群的共轭类图和素图等，以及环的单位凯莱图等。

本文所涉及的群均为有限群。设G是一个群且 $g\in G$，g的阶 $o\left(g\right)$ 是最小的正整数n使得 $g^n=e$，其中e是G的单位元。给定一个群G，G上幂图是一个以G为顶点集合的简单图，其中两个元素之间有边的充分必要条件是在G中这两个元素一个可以写成另外一个的幂。在2000年，Kelarev和Quinn [1] 首次引入了群的有向幂图，在2009年，Chakrabarty、Ghosh和Sen [2] 首次引入了群的无向幂图，也简称为群的幂图。近十多年来，学者对幂图的研究非常活跃，看综述文章 [3]。为了减少群幂图中的一些边，Rajkumar和Anitha [4] 介绍了群G的简化幂图 $RP\left(G\right)$，该图是以G的所有元素为顶点集合的一个简单图，其中两个不同的元素 $x,y$ 相连接的充分必要条件是 $\langle x\rangle \subset \langle y\rangle$ 或 $\langle y\rangle \subset \langle x\rangle$, 其中 $\langle x\rangle$ 表示由元素x生成的的循环子群。换句话说，群G的简化幂图是从群G的幂图中删除所有满足条件 $\langle x\rangle =\langle y\rangle$ 的边 $\left\{x,y\right\}$。因此 $RP\left(G\right)$ 是群G的幂图的一个生成子图。在 [4] 中，这两位学者主要研究了群的简化幂图的图理论性质对群结构的影响。

在图理论中，寻找图的具有最大基数的独立集被称为最大独立集问题。众所周知，计算一个图的独立数问题和计算图的团数问题均是NP-困难的。本文将给出14阶以内的非交换群的简化幂图的结构。此外本文也求了这些群简化幂图的独立数、团数以及彩虹连通数。

2. 小阶数的非交换群的简化幂图

本节将给出14阶以内的非交换群的简化幂图的结构。从有限群的分类可知，所有14阶以内的非交换群有 $S_3,D_4,Q_8,D_5,A_4,D_6,Q_{12},D_7$，其中 $Q_8,A_4,Q_{12}$ 分别是8阶的四元数群、4次交错群和12阶双循环群。下面是对14阶以内的非交换群的简化幂图的简短描述。

(i) $S_3=\left\{e,\left(12\right),\left(13\right),\left(23\right),\left(123\right),\left(132\right)\right\}$，其中 ${\left(12\right)}^2={\left(13\right)}^2={\left(23\right)}^2=e$， ${\left(123\right)}^2=\left(132\right)$， ${\left(132\right)}^2=\left(123\right)$， ${\left(123\right)}^3={\left(132\right)}^3=e$。因此 $\left\{\left(12\right),\left(13\right),\left(23\right)\right\}$ 中每个元素的阶是2，同理(123)和(132)的阶是3。因此可得出 $S_3$ 的简化幂图 $RP\left(S_3\right)$ 如图1所示。

Figure 1. $RP(\; S\; 3\; )$

图1. $RP(\; S\; 3\; )$

(ii) $D_4=\left\{e,a,a^2,a^3,b,ab,a^{2}b,a^{3}b\right\}$，其中 $o\left(a\right)=4$， $o\left(b\right)=2$， $ba=a^{3}b$。一个简单的计算表明 $o\left(a^3\right)=4$， $o\left(a^2\right)=o\left(ab\right)=o\left(a^{2}b\right)=o\left(a^{3}b\right)=2$。我们可以得出：所有的 $\left\{b,ab,a^{2}b,a^{3}b\right\}$ 都只与e相邻，因此可得出 $D_4$ 的简化幂图 $RP\left(D_4\right)$ 如图2所示。从图2可以求出 $D_4$ 的团数为3，独立数为6。

Figure 2. $RP(\; D\; 4\; )$

图2. $RP(\; D\; 4\; )$

(iii) $Q_8=\left\{e,a,a^2,a^3,b,ab,a^{2}b,a^{3}b\right\}$，式中 $o\left(a\right)=4$， $a^2=b^2$， $ba=a^{3}b$。很容易验证， $b^2={\left(a^3\right)}^2={\left(ab\right)}^2={\left(a^{2}b\right)}^2={\left(a^{3}b\right)}^2=a^2$， $o\left(a^2\right)=2$。这些结果表明，除了e和 $a^2$ 的阶为2外，每个元素的阶数都是4。 $\left\{e,a,a^2,a^3\right\}$， $\left\{e,b,a^2,a^{2}b\right\}$， $\left\{e,ab,a^2,a^{3}b\right\}$ 都是 $Q_8$ 的循环子群，阶数为4。因此可得出 $Q_8$ 的简化幂图 $RP\left(Q_8\right)$ 如图3所示。从图3可以求出 $Q_8$ 的团数为4，独立数为6。

(iv) $D_5=\left\{e,a,a^2,a^3,a^4,b,ab,a^{2}b,a^{3}b,a^{4}b\right\}$，其中 $o\left(a\right)=5$， $o\left(b\right)=2$， $ba=a^{4}b$。简单计算表明， $o\left(a^2\right)=o\left(a^3\right)=o\left(a^4\right)=5$， $o\left(ab\right)=o\left(a^{2}b\right)=o\left(a^{3}b\right)=o\left(a^{4}b\right)=2$。我们可以得出：所有 $\left\{b,ab,a^{2}b,a^{3}b,a^{4}b\right\}$ 只与e相邻，因此可得出 $D_5$ 的简化幂图 $RP\left(D_5\right)$ 如图4所示。从图4可以求出 $D_5$ 的团数为2，独立数为9。

(v) $A_4=\left\{e,\left(123\right),\left(132\right),\left(124\right),\left(142\right),\left(134\right),\left(143\right),\left(234\right),\left(243\right),\left(12\right)\left(34\right),\left(13\right)\left(24\right),\left(14\right)\left(23\right)\right\}$，其中 $o\left(\left(12\right)\left(34\right)\right)=o\left(\left(13\right)\left(24\right)\right)=o\left(\left(14\right)\left(23\right)\right)=2$，且 $\left\{e,\left(123\right),\left(132\right)\right\}$， $\left\{e,\left(124\right),\left(142\right)\right\}$， $\left\{e,\left(134\right),\left(143\right)\right\}$， $\left\{e,\left(234\right),\left(243\right)\right\}$ 都是3阶 $A_4$ 的循环子群。所以可得 $A_4$ 简化幂图 $RP\left(A_4\right)$，如图5所示。

Figure 3. $RP(\; Q\; 8\; )$

图3. $RP(\; Q\; 8\; )$

Figure 4. $RP(\; D\; 5\; )$

图4. $RP(\; D\; 5\; )$

Figure 5. $RP(\; A\; 4\; )$

图5. $RP(\; A\; 4\; )$

(vi) $D_{\text{6}}=\left\{e,a,a^2,a^3,a^4,a^5,b,ab,a^{2}b,a^{3}b,a^{4}b,a^{5}b\right\}$，其中 $o\left(a\right)=6$， $o\left(b\right)=2$， $ba=a^{5}b$。简单的计算表明， $o\left(a^3\right)=o\left(ab\right)=o\left(a^{2}b\right)=o\left(a^{3}b\right)=o\left(a^{5}b\right)=2$， $o\left(a^2\right)=o\left(a^4\right)=3$， $o\left(a^5\right)=6$， ${\left(a^5\right)}^3=a^3$。因此所有的 $\left\{b,ab,a^{2}b,a^{3}b,a^{4}b,a^{5}b\right\}$ 都只与e相邻， $a^3$ 与所有的 $\left\{e,a,a^5\right\}$ 相邻。所以可得 $D_6$ 简化幂图 $RP\left(D_6\right)$，如图6所示。

(vii) $Q_{12}=\left\{e,a,a^2,a^3,a^4,a^5,b,ab,a^{2}b,a^{3}b,a^{4}b,a^{5}b\right\}$，其中 $o\left(a\right)=6$， $a^3=b^2$， $ba=a^{5}b$。很容易验证 $o\left(b\right)=o\left(ab\right)=o\left(a^{2}b\right)=o\left(a^{3}b\right)=o\left(a^{4}b\right)=o\left(a^{5}b\right)=4$， $o\left(a^2\right)=3$， $o\left(a^3\right)=2$， $o\left(a^5\right)=6$， ${\left(a^5\right)}^3=a^3$。所以可得 $Q_{12}$ 简化幂图 $RP\left(Q_{12}\right)$，如图7所示。

Figure 6. $RP(\; D\; 6\; )$

图6. $RP(\; D\; 6\; )$

Figure 7. $RP(\; Q\; 12\; )$

图7. $RP(\; Q\; 12\; )$

(viii) $D_7=\left\{e,a,a^2,a^3,a^4,a^5,a^{\text{6}},b,ab,a^{2}b,a^{3}b,a^{4}b,a^{5}b,a^{6}b\right\}$，其中 $o\left(a\right)=7$， $o\left(b\right)=2$， $ba=a^{6}b$。简单计算表明， $o\left(a^2\right)=o\left(a^3\right)=o\left(a^4\right)=o\left(a^6\right)=7$， $o\left(ab\right)=o\left(a^{2}b\right)=o\left(a^{3}b\right)=o\left(a^{4}b\right)=o\left(a^{5}b\right)=o\left(a^{6}b\right)=2$。所以可得 $D_7$ 简化幂图 $RP\left(D_7\right)$，如图8所示。

Figure 8. $RP(\; D\; 7\; )$

图8. $RP(\; D\; 7\; )$

3. 小阶数的非交换群的简化幂图的一些参数

在图 $\Gamma$ 上定义一个边染色 $\zeta :E\left(\Gamma \right)\to \left\{1,2,\cdots ,k\right\}$， $k\in N$，其中相邻的边可以被染成相同的颜色。如果在该染色 $\zeta$ 之下，一条路P上的任两条边的颜色都不同，则P称为一条彩虹路。如果对于图 $\Gamma$ 的任两个不同的顶点u和v，均存在一条彩虹路连接这两个顶点，则 $\Gamma$ 称为一个彩虹连通图，并且 $\zeta$ 称为 $\Gamma$ 的一个彩虹k-染色。使得 $\Gamma$ 彩虹连通的最少的颜色数称为 $\Gamma$ 的彩虹连通数。

本节根据图数、独立数以及彩虹连通数的定义，得到14阶以内的非交换群对应的简化幂图的这些参数值(见表1)。

Table 1. Reduced power graphs corresponding to non-commutative groups of order 14

表1. 14阶以内的非交换群对应的简化幂图

基金项目

本文得到国家级大学生创新创业训练项目(201910705028)的资助。