关于小阶数非交换群的简化幂图 On the Reduced Power Graphs of Non-Abelian Groups of Small Order

doi:10.12677/AAM.2020.911230

Advances in Applied Mathematics
Vol. 09 No. 11 ( 2020 ), Article ID: 38780 , 6 pages
10.12677/AAM.2020.911230

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

仪钰婷，吴玥雯，安佳薇

●How to Cite this Article

西安石油大学理学院，陕西西安

收稿日期：2020年11月1日；录用日期：2020年11月18日；发布日期：2020年11月25日

摘要

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

关键词

简化幂图，独立数，有限群，团数，彩虹连通数

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

Yuting Yi, Yuewen Wu, Jiawei An

School of Science, Xi'an Shiyou University, Xi'an Shaanxi

Received: Nov. 1^st, 2020; accepted: Nov. 18^th, 2020; published: Nov. 25^th, 2020

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 $〈 x 〉 \subset 〈 y 〉$ or $〈 y 〉 \subset 〈 x 〉$ . 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.

Keywords:Reduced Power Graph, Independence Number, Finite Group, Clique Number, Rainbow Connection Number

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

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

1. 引言

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

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

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

Figure 1. $R P ( S 3 )$

图1. $R P ( S 3 )$

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

Figure 2. $R P ( D 4 )$

图2. $R P ( D 4 )$

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

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

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

Figure 3. $R P ( Q 8 )$

图3. $R P ( Q 8 )$

Figure 4. $R P ( D 5 )$

图4. $R P ( D 5 )$

Figure 5. $R P ( A 4 )$

图5. $R P ( A 4 )$

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

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

Figure 6. $R P ( D 6 )$

图6. $R P ( D 6 )$

Figure 7. $R P ( Q 12 )$

图7. $R P ( Q 12 )$

(viii) $D_{7} = {e, a, a^{2}, a^{3}, a^{4}, a^{5}, a^{6}, b, a b, a^{2} b, a^{3} b, a^{4} b, a^{5} b, a^{6} b}$ ，其中 $o (a) = 7$ ， $o (b) = 2$ ， $b a = a^{6} b$ 。简单计算表明， $o (a^{2}) = o (a^{3}) = o (a^{4}) = o (a^{6}) = 7$ ， $o (a b) = o (a^{2} b) = o (a^{3} b) = o (a^{4} b) = o (a^{5} b) = o (a^{6} b) = 2$ 。所以可得 $D_{7}$ 简化幂图 $R P (D_{7})$ ，如图8所示。

Figure 8. $R P ( D 7 )$

图8. $R P ( D 7 )$

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

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

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

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

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

基金项目

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

文章引用

仪钰婷,吴玥雯,安佳薇. 关于小阶数非交换群的简化幂图
On the Reduced Power Graphs of Non-Abelian Groups of Small Order[J]. 应用数学进展, 2020, 09(11): 1990-1995. https://doi.org/10.12677/AAM.2020.911230

参考文献

1. Kelarev, A.V. and Quinn, S.J. (2000) A Combinatorial Property and Power Graphs of Groups. Contributions to General Algebra, 12, 229-235.

2. Chakrabarty, I., Ghosh, S. and Sen, M.K. (2009) Undirected Power Graphs of Semigroups. Semigroup Forum, 78, 410-426. https://doi.org/10.1007/s00233-008-9132-y

3. Abawajy, J., Kelarev, A.V. and Chowdhury, M. (2013) Power Graphs: A Survey. Electronic Journal of Graph Theory and Applications, 1, 125-147. https://doi.org/10.5614/ejgta.2013.1.2.6

4. Rajkumar, R. and Anitha, T. (2017) Reduced Power Graph of a Group. Electronic Notes in Discrete Mathematics, 63, 69-76. https://doi.org/10.1016/j.endm.2017.10.063

期刊菜单