关于有限群的交集幂图与幂图之间的区别

《Discrete Mathematics》：On the difference of the intersection power graph and the power graph of a finite group

　　摘要
有限群G的差分图D(G)是通过取G的交集幂图和幂图的（边）差分，然后移除所有孤立顶点得到的图。在本文中，我们给出了关于差分图的一些结果。我们研究了幂图和交集幂图相同的群，并对差分图中的孤立顶点进行了一些观察。我们探讨了差分图相对于底层群G的各种性质的连通性和完美性。此外，我们还研究了图的双重简化操作，这是一种可以得到更易于分析的更小图的技术。

引言
在过去二十年中，与各种代数结构相关的图的研究受到了相当大的关注。这样的研究在以下方面非常有用：(1)表征生成的图；(2)表征产生同构图的代数结构；(3)理解代数结构及其对应图之间的相互依赖性。人们引入了多种图来通过图论方法探索代数结构的性质。值得注意的例子包括交换图[9]、生成图[23]、幂图[18]、[27]以及增强幂图[1]、[5]、[6]。幂图的概念最初由Kelarev和Quinn在半群理论中引入[26]，而交集幂图则是在[4]中引入的。
在本文中，我们定义了群的幂图和交集幂图。为了比较，我们还定义了增强幂图，尽管我们没有研究这种图。在整篇文章中，我们考虑的所有群G都是有限的。设π(G)={p∈N：p是素数且p|G|}表示|G|的素数因子集合。类似地，对于a∈G，设π(a)={p∈N：p是素数且p|o(a)}表示a的阶的素数因子集合。

定义1.1 [4]
设G是一个具有单位元e的群。
(1) G的交集幂图，记为GI(G)，是一个顶点集为G的图，当且仅当存在一个非单位元z∈G使得z既是x的幂也是y的幂时，两个不同的非单位顶点x和y是相邻的；等价地说，〈x〉∩〈y〉≠{e}。按照惯例，我们将e与G中的所有其他顶点相邻，其中e是群G的单位元。
(2) G的幂图P(G)是一个顶点集为G的图，当且仅当其中一个顶点是另一个顶点的幂时，两个顶点x和y是相邻的。
(3) G的增强幂图Pe(G)是一个顶点集为G的图，当且仅当存在u∈G使得x和y都是u的幂时，两个顶点x和y是相邻的。

注释1.1
幂图在文献中受到了很多关注：参见[27]以获取综述。对于交集幂图的关注较少：参见[4]。它在[12]中以“对偶增强幂图”的名称被简要讨论过。
显然，如果x和y在G的幂图中是相邻的，那么它们在交集幂图和增强幂图中也是相邻的；换句话说，幂图是其他两个图的生成子图。这激发了对两种差分图的研究：一种差分图中包含的是增强幂图中不是幂图的边；另一种差分图中包含的是幂图中不是幂图的边。第一种差分图在[7]中进行了研究，在这里不再赘述；我们的目的是研究第二种差分图。

定义1.2
有限群G的未删除差分图D(G)是G的交集幂图和幂图的（边）差分，而G的差分图D(G)是通过删除D(G)中所有孤立顶点得到的D(G)的子图。
图D(G)可以从G的循环子群的半格构建如下。设G是一个有限群，令L(G)表示G的循环子群的半格。设B1(G)是一个简单的无向图，其顶点集为L(G)，当且仅当S?T、T?S且S∩T≠{e}（其中e表示G的单位元）时，两个顶点S,T∈L(G)是相邻的。设B(G)为基图，它是从B1(G)中移除所有孤立顶点得到的图。然后通过用大小为|V(S)|=φ(|S|)的独立集V(S)替换每个顶点S来从B(G)得到图D(G)，其中φ表示欧拉函数，使得在D(G)中x～y当且仅当存在L(G)中的S≠T，x∈V(S)，y∈V(T)，并且S～T在B(G)中。

问题的提出
在这个定义之后，首先应该提出的问题是：
问题1.1
给定一个群G，识别未删除差分图D(G)中的孤立顶点。特别是，哪些群具有D(G)没有边的性质？空图是一个没有边但顶点集非空的图，而空图则顶点集为空。注意，一个群G具有D(G)没有边的性质当且仅当G的交集幂图和幂图相等。我们将在第5节进一步讨论孤立顶点的问题，并在第2节和第7节讨论何时它是空图的问题。

注释1.2
一个类似的问题，即确定幂图和增强幂图相等的群，已经得到解决[1]。这些恰好是EPPO群，即每个元素的阶都是素数的幂。在Higman和Suzuki的初步工作之后，Brandl在1981年对这些群进行了分类。（一个可能更容易理解的版本出现在综述[16]中。）我们希望幂图和交集幂图相等的群也构成一个有趣的类别。

本文的组织结构如下。在本节中，我们介绍了与有限群G相关的幂图、交集幂图和差分图D(G)，并讨论了激发我们研究的问题。在第2节中，我们研究了D(G)为空的有限群G，并记录了关于孤立顶点的几个观察结果。第3节发展了差分图的基本理论。我们建立了涉及G的生成元的邻接性标准，并证明每个有限图都作为某个有限群G的D(G)的诱导子图出现。在第4节中，我们研究了D(G)的连通性。这项研究的动机来自于Aalipour等人在[1, Question 40]中对幂图连通性的问题，随后Cameron和Jafari在[14]中给出了答案，以及Bera、Dey和Mukherjee对增强幂图的类似结果[6]。第5节描述了D(G)为空的有限p-群G，特别关注广义四元数群。第6节我们研究了D(G)的完美性、二分性和欧拉性质。这项研究的动机是幂图总是完美的[2, Thm. 5]，而尽管已知它们关于色数和弱完美性的结果，增强幂图的完美性仍然是一个未解决的问题[17]。第7节表明，D(G)为空的非阿贝尔有限简单群正是命题7.2中列出的那些群。第8节讨论了具有唯一对合的群，第9节通过Mathieu群M11说明了通用理论。最后，在第10节中，我们讨论了未解决的问题，包括孤立顶点的分类以及当π(Z(G))≤1时D(G)的完美性、二分性和连通性的确定。

当差分图为空时？
在本节中，我们研究了幂图和交集幂图相等的群，即那些差分图D(G)为空的群，或者等价地，未删除差分图D(G)是空图的群。我们还对未删除差分图D(G)中的孤立顶点进行了一些观察。我们从一个简单的结果开始，表明未删除差分图与许多其他关于群的图具有相同的性质。

基本性质
在本节中，我们回顾了一些已知的结果，并建立了一些在后续章节中起关键作用的引理。此外，我们证明了差分图是普遍的。

引理3.1 [5]
设G是一个p-群。那么G的阶为p的不同子群的个数要么是1，要么至少是3。

引理3.2 [21, Theorem 5.4.10]
如果G是一个具有阶为奇素数p的唯一子群的p-群，那么G是循环的。

引理3.3 [4]
设G是一个群。那么群G的交集幂图GI(G)是完全图当且仅当

当差分图是连通的时？
在本节中，我们研究了差分图是连通的群。在连通的情况下，我们确定了这些差分图的直径界限；在非连通的情况下，我们对它们的孤立顶点进行了一些观察。我们在此方面的主要定理如下：

定理4.1
设G是一个有限群，且π(Z(G))≥2。那么差分图D(G)是连通的当且仅当G?Zpq（其中p,q是素数）。此外，当连通时，diam(D(G))≤6。

当G是一个p-群时
在本节中，我们研究了幂图和交集幂图相同的有限p-群，等价地，那些差分图为空的群。我们还讨论了这类差分图中孤立顶点的观察结果。

定理5.1
设G是一个有限p-群。那么D(G)是一个空图当且仅当G满足以下条件之一：
(1) G是一个循环p-群。
(2) G是至少三个循环子群的并集，这些子群之间的交集是平凡的。

差分图的完美性、二分性和欧拉性质
在本节中，我们解决了以下关于具有π(Z(G))≥2的有限群G的基本问题：
• 差分图D(G)何时是完美的？
• 在什么条件下D(G)是二分图？
• D(G)何时具有欧拉路径？

我们提出了一个完整的特征描述，用于那些|π(Z(G))|≥2且D(G)是二分图的有限群G。此外，我们探讨了D(G)的完美性和欧拉性质，揭示了它们的结构和组合含义。

定理6.1
设G是一个有限...
回忆一下差分图为空的群类C。在本节中，我们确定了D(G)为空的非阿贝尔简单群G。由于这些群的中心是平凡的，根据定理2.2，要判断G是否属于C，只需考虑这样的群的真子群是否属于C。这样的群只有G=PSL(2,q)对于某些素数幂q，尽管确定哪些素数幂出现似乎超出了数论的范围。

具有唯一对合的群
具有唯一对合的群类在不同领域中有许多出现；例如，它包含二进制多面体群[19, p. 82]，这些群在John McKay的著名观察中起到了作用，他将正多面体与异常根系联系起来（在[13, pp. 109f]中讨论）。

设G是一个包含唯一对合z的群。那么G中偶数阶的元素集F至少包含G的一半元素（因为对于每一对(g,gz)，至少有一个属于F）。

在论文[7]中，作者采用了各种小的有限简单群（阶小于10^4），构建了幂图和增强幂图的差分，对这个图进行了完全的双重简化，并检查了结果。对于大多数测试的图，结果并不有趣；要么图被简化为一个顶点，要么它有许多同构的连通分量。对于阶为7920的Mathieu群M11，找到了一个有趣的图；

结论和开放问题
在本文中，我们研究了有限群G的差分图D(G)。这项调查主要关注于识别图D(G)中的孤立顶点，特别是确定哪些顶点组合能够形成无边的差图（difference graph），同时研究这类图的连通性和完美性。这项工作引发的一些问题为后续研究指明了方向。对于一个满足条件π(Z(G))≥2的有限群G，研究表明D(G)是连通的，并且其直径不超过6。

致谢
作者们衷心感谢审稿人对手稿的仔细阅读以及提出的宝贵意见和建议，这些帮助显著提升了本文的表述质量和学术水平。SB特别感谢印度国家高等数学委员会（NBHM）提供的财务支持（项目编号：02011/29/2025NBHM(R.P)/R&D II/11951），并对委员会表示诚挚的感谢。此外，SB还要感谢Sudip Bera和Peter J. Cameron的相关贡献。