On Some Bi-Cayley Graphs over Cyclic Groups of Order $p^2 q^2$ and Related Extensions

本文研究了阶为 $p^2q^2$（$p, q$ 为不同素数）的循环群上的双凯莱图，阐明了其连通性、正则性、围长为 3 及直径为 5 等关键组合性质，并将部分结论推广至满足特定连接集条件的任意有限群情形。

要点

这篇论文就像是在研究一种特殊的**“双生城市”**的地图设计。

想象一下，你是一位城市规划师，你的任务不是设计一座普通的城，而是设计两座完全一样的城（我们叫它们**“左城”和“右城”**），然后在这两座城之间架起桥梁，把它们连成一个超级大社区。

这篇论文就是关于如何设计这种“双生城市”的数学规则，特别是当城市里的居民数量非常特殊（是 $p^2q^2$ 这种形式，其中 $p$ 和 $q$ 是像 2、3、5 这样的“素数”）时，这个社区会呈现出什么样的性格。

下面我用几个生动的比喻来解释论文里的核心发现：

1. 什么是“双凯莱图”（Bi-Cayley Graph）？

• 普通凯莱图：就像一座城，每个人（顶点）都按照固定的规则（比如“向右走 3 步”）和邻居打招呼。
• 双凯莱图：现在你有两座一模一样的城。
  • 左城里的人，只和左城里的人按规则 A 打招呼。
  • 右城里的人，只和右城里的人按规则 B 打招呼。
  • 关键点：左城的每个人，都有一条专属的“独木桥”直接连到右城对应的那个人。
  • 这就构成了一个巨大的、由两部分组成的社交网络。

2. 这座“双生城市”连通吗？（连通性）

• 问题：如果你站在左城的某个角落，能走到右城的任何地方吗？
• 发现：是的，一定能。
• 比喻：只要右城内部的路网是通的（论文证明了右城内部是连通的），那么通过“独木桥”，左城的人也能去右城，反之亦然。整个大社区是紧密相连的，没有孤岛。

3. 最短的“八卦圈”有多长？（围长 Girth）

• 问题：在这个社区里，最短的“转一圈回到原点”的路线需要走几步？
• 发现：只需要 3 步。
• 比喻：这意味着社区里充满了“小三角”关系。比如 A 认识 B，B 认识 C，C 又认识 A。这种紧密的三角关系在左城或右城内部非常普遍，所以最短的圈子就是三角形。

4. 最大的“小团体”有多大？（团数 Clique Number）

• 问题：在这个社区里，最多能有多少人互相都认识（两两相连）？
• 发现：这个最大团的大小取决于 $p$ 和 $q$ 哪个更大，取较大的那个数。
• 比喻：想象 $p$ 和 $q$ 是两种不同颜色的“超级粉丝团”。左城和右城里，最大的朋友圈子大小，就是这两种粉丝团里人数较多的那个团的大小。而且，这种大圈子通常只存在于左城或右城内部，很难跨越两座城形成更大的圈子。

5. 给居民发“颜色”需要几种？（色数 Chromatic Number）

• 问题：如果要给每个人发帽子，要求相邻的人（互相认识的）不能戴同色帽子，最少需要几种颜色？
• 发现：需要的颜色数量是 $\max(p, q) + 1$。
• 比喻：这就像给城市分区。因为两座城之间每个人都有“独木桥”相连（左城的 A 和右城的 A 必须戴不同颜色），这增加了一层限制。虽然左城和右城内部各自只需要 $p$ 或 $q$ 种颜色，但为了避开“独木桥”带来的冲突，我们需要额外多准备一种颜色，总共就是“较大数 + 1"。

6. 从最远两端走多远？（直径 Diameter）

• 问题：在这个社区里，两个人之间最远需要走几步才能见面？
• 发现：最远只需要 5 步。
• 比喻：这是一个非常高效的社区！哪怕你住在左城的最角落，想找右城最角落的某人，你只需要：
  1. 在左城走几步；
  2. 过桥；
  3. 在右城走几步。
     论文证明，无论城市多大，这个“最远距离”被死死地限制在 5 步以内。这意味着信息在这个网络里传播得飞快。

7. 最大的“互不认识”群体有多大？（独立数 Independence Number）

• 问题：最多能选出多少人，让他们彼此之间都不认识（没有连线）？
• 发现：这是一个复杂的计算，大致是 $2pq \times \min(p, q)$ 减去一些重叠部分。
• 比喻：想象你要组织一个“互不认识的派对”。因为左城和右城内部有很多紧密的小圈子，你很难选出太多人。论文通过精细的数学推导，算出了这个派对的最大人数上限。

8. 更有趣的扩展：如果“桥”变多了怎么办？

论文最后还做了一个大胆的实验：如果连接左右两城的“桥”不仅仅是 1 对 1 的独木桥，而是每个人都可以和右城的**所有“倒立者”（对合元，即自己-inverse 的人）**连桥，会发生什么？

• 比喻：这就好比左城的每个人，不仅能连到右城的对应人，还能连到右城所有“性格相反”的人。
• 发现：这种结构会让两座城之间的联系变得极其紧密，甚至可能让原本不连通的部分瞬间连通。这展示了这种数学结构的灵活性。

总结

这篇论文就像是在给一种特殊的**“双生网络”**做体检。它告诉我们：

1. 这种网络非常紧密（直径短，全是小三角）。
2. 它高度对称（左右两边结构相似但又有区别）。
3. 它的性格（比如需要多少颜色、最大圈子多大）完全由底层的数字规则（$p$ 和 $q$）决定。

作者不仅算出了这些具体数字，还证明了这些规律不仅仅适用于这种特殊的数字，甚至可以推广到更广泛的数学结构中。这就像是从一个具体的“双生城市”案例中，提炼出了一套通用的“双城规划学”原理。

技术摘要

这是一份关于论文《On Some Bi-Cayley Graphs over Cyclic Groups of Order $p^2q^2$ and Related Extensions》（关于 $p^2q^2$ 阶循环群上的一些双凯莱图及其相关推广）的详细技术总结。

1. 研究问题 (Problem)

本文主要研究定义在循环群 $G \cong \mathbb{Z}_{p^2q^2}$ 上的**双凯莱图（Bi-Cayley graphs）**的结构与组合性质，其中 $p$ 和 $q$ 是两个不同的素数。

• 背景：凯莱图（Cayley graphs）是代数图论中的核心概念，将群结构编码为图。双凯莱图是凯莱图的自然推广，由两个不相交的群副本组成，通过三个连接集（$S_1, S_2, S_3$）定义边。
• 具体挑战：
  • 现有的研究多集中在凯莱图或一般双凯莱图的对称性上，缺乏针对特定阶数（如 $p^2q^2$）和特定连接集（基于元素阶数）的双凯莱图的精确组合不变量分析。
  • 需要确定此类图的关键参数：连通性、正则性、围长（girth）、团数（clique number）、色数（chromatic number）、直径（diameter）和独立数（independence number）。
  • 需要探讨这些结果是否可以推广到更一般的有限群，特别是当连接集 $S_3$ 包含所有对合元（involutions）时的情况。

2. 方法论 (Methodology)

作者采用了代数图论与群论相结合的方法，具体步骤如下：

1. 群结构分解：利用中国剩余定理，将循环群 $\mathbb{Z}_{p^2q^2}$ 分解为 $\mathbb{Z}_{p^2} \times \mathbb{Z}_{q^2}$。群元素表示为有序对 $(g_p, g_q)$，这使得邻接条件可以按分量进行分析。
2. 连接集定义：
   • $S_1 = \{x \in G : |x| = p \text{ 或 } q\}$
   • $S_2 = \{x \in G : |x| = p^2 \text{ 或 } q^2\}$
   • $S_3 = \{e_G\}$（在主要部分中，$S_3$ 仅包含单位元，连接两个副本的对应顶点）。
3. 子图分析：将双凯莱图 $\Gamma$ 分解为两个诱导子图：
   • $\Gamma_0$（0 侧）：由 $S_1$ 生成的凯莱图。
   • $\Gamma_1$（1 侧）：由 $S_2$ 生成的凯莱图。
   • 分析这两个子图的结构（如是否同构于完全多部图的笛卡尔积），进而推导整体图的性质。
4. 组合推导：
   • 利用鸽巢原理（Pigeonhole Principle）和计数论证来推导色数和独立数。
   • 通过构造具体的路径来估算直径。
   • 利用群生成性质（如 $S_2$ 生成整个群）证明连通性。
5. 推广与扩展：
   • 将部分结论推广到任意有限群。
   • 特别研究了 $S_3$ 为群 $G$ 中所有对合元集合 $I(G)$ 的情况，引入了“交叉边子图”（cross-edges subgraph）的概念，并分析了混合团（mixed clique）的性质。

3. 主要贡献与结果 (Key Contributions & Results)

A. 针对 $p^2q^2$ 阶循环群的具体结果

1. 基本性质：

   • 顶点数：$2p^2q^2$。
   • 边数：$\frac{p^2q^2(p^2 + q^2)}{2}$。
   • 正则性：图是**双正则（biregular）**的。
     • 0 侧顶点度数为：$p(p-1) + q(q-1) + 1$。
     • 1 侧顶点度数为：$p + q - 1$。
   • 连通性：图是连通的（因为 $S_2$ 生成整个群，且 $S_3$ 连接两侧）。
   • 欧拉性：由于顶点度数均为奇数，该图不是欧拉图。

2. 围长 (Girth)：

   • 围长为 3。证明表明任何长度为 3 的圈必须完全位于同一侧（$\Gamma_0$ 或 $\Gamma_1$），且由于 $S_1$ 中包含阶为 $p$ 和 $q$ 的元素，必然存在三角形。

3. 团数 (Clique Number, $\omega(\Gamma)$)：

   • 结果为 $\max\{p, q\}$。
   • 证明指出，任何大小大于 2 的团必须完全位于 $\Gamma_0$ 或 $\Gamma_1$ 内部，不能跨越两侧。通过分析子图中的最大团（分别同构于完全 $p$-部图和 $q$-部图的子结构），得出最大团大小为 $\max\{p, q\}$。

4. 色数 (Chromatic Number, $\chi(\Gamma)$)：

   • 结果为 $\max\{p, q\} + 1$。
   • 虽然子图 $\Gamma_0$ 和 $\Gamma_1$ 的色数均为 $\max\{p, q\}$，但由于两侧对应顶点 $(0, g)$ 和 $(1, g)$ 相连，且无法用 $\max\{p, q\}$ 种颜色同时满足两侧的不冲突条件（通过鸽巢原理证明矛盾），因此需要增加一种颜色。

5. 直径 (Diameter, $\text{diam}(\Gamma)$)：

   • 结果为 5。
   • 分析表明，$\Gamma_1$ 的直径为 4，$\Gamma_0$ 的直径为 2（但在不同连通分量间需通过 $\Gamma_1$ 跳转）。最坏情况下的路径长度为 5。

6. 独立数 (Independence Number, $\alpha(\Gamma)$)：

   • 结果为 $2pq \min{p, q} - \min{p^2, q^2}$。
   • 通过构造 $\Gamma_0$ 和 $\Gamma_1$ 的最大独立集，并计算它们在对应顶点上的重叠部分（overlap），得出了精确公式。

B. 推广到任意有限群的结果

1. 一般性结论：

   • 连通性取决于 $S_1$ 或 $S_2$ 是否生成群 $G$。
   • 团数公式为 $\omega(\Gamma) = \max\{\omega(\Gamma_0), \omega(\Gamma_1), 2\}$。
   • 色数满足不等式：$\max\{\chi(\Gamma_0), \chi(\Gamma_1)\} \le \chi(\Gamma) \le 1 + \max\{\chi(\Gamma_0), \chi(\Gamma_1)\}$。

2. 基于对合元 ($S_3 = I(G)$) 的扩展：

   • 当 $S_3$ 为群 $G$ 的所有对合元集合时，引入了“交叉边子图” $\Gamma_{ce}$。
   • 证明了 $\Gamma_{ce}$ 是 $|I(G)|$-正则的。
   • 定义了混合团（mixed clique）（跨越两侧的团），并在 $S_1, S_2$ 满足“对合分离（involution-separating）”性质时，给出了混合团大小的限制（一侧最多包含 2 个顶点）。

4. 意义与影响 (Significance)

1. 填补研究空白：本文首次系统地给出了 $p^2q^2$ 阶循环群上特定连接集定义的双凯莱图的精确组合参数（如色数、直径、独立数），弥补了现有文献多关注对称性而缺乏具体参数计算的不足。
2. 揭示结构差异：通过对比凯莱图与双凯莱图，揭示了双凯莱图由于“双副本”结构带来的额外复杂性（如色数增加 1、直径扩大等），阐明了连接集 $S_3$ 对全局性质的决定性作用。
3. 方法论的普适性：虽然主要结果基于循环群，但作者成功地将部分核心论证（如连通性判定、团数上界、色数界限）推广到了任意有限群，为研究更广泛的双凯莱图提供了理论框架。
4. 代数与组合的桥梁：文章展示了如何利用群的代数性质（如元素阶、子群结构、对合元）来精确控制图的组合不变量，体现了代数图论在解决复杂图参数问题上的强大能力。

综上所述，该论文通过严谨的代数推导和组合构造，不仅解决了特定阶数双凯莱图的具体参数问题，还建立了一套分析此类图结构的通用方法，对代数图论领域具有重要的参考价值。