技术摘要：二元 LCD 码及其图表示

问题陈述

本文解决了刻画哪些简单图（无自环或多重边的图）通过其邻接矩阵生成二元线性互补对偶（LCD）码这一基本问题。尽管先前的研究已建立了图谱与码长之间的联系，并为特定图族（如强正则图）生成 LCD 码提供了充分条件，但完整的刻画尚属空白。此外，虽然已知 LCD 码的码等价性与图的同构性可归约至图同构（GI）问题，但此前缺乏一种能够利用编码理论工具对图进行系统分类的构造性双射。

核心挑战在于确定图的邻接矩阵 $A$ 在 $\mathbb{F}_2$ 上为幂等矩阵（即 $A^2 = A$）的充要条件，因为该性质等价于 $A$ 的行空间构成一个 LCD 码。

方法论

作者采用结合代数编码理论与代数图论的双重方法：

1. 正交投影与幂等性：本文利用了一个结构性质，即二元码 $C$ 是 LCD 码当且仅当其正交投影算子 $\Pi_C$ 是一个满足 $\Pi_C^2 = \Pi_C$ 的对称矩阵。作者证明，对于二元偶 LCD 码，该投影算子恰好对应于某个简单图的邻接矩阵。
2. 组合刻画：通过分析 $\mathbb{F}_2$ 上的幂等条件 $A^2 = A$，本文推导出了对图结构的组合约束，具体涉及顶点度数以及相邻与非相邻顶点之间公共邻居的数量关系。
3. 距离正则图（DRG）分析：本文应用了距离正则图距离矩阵的三项递推关系。这使得幂等条件能够转化为对交集数组参数 $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ 的显式奇偶性约束。
4. 分类的质量公式：为了对具有幂等邻接矩阵的图进行分类，本文利用了 Carlet 等人开发的二元 LCD 码的现有质量公式。通过建立不等价码与非同构图之间的双射，作者避免了穷举图枚举，而是利用已知的 LCD 码分类来推断相应图的分类。

主要贡献

1. 距离正则图的充要刻画

本文提供了生成二元偶 LCD 码的距离正则图的完整刻画。对于具有交集数组 $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ 的距离正则图，其邻接矩阵生成 LCD 码当且仅当：

• $b_0 \equiv 0 \pmod 2$（度数为偶数）；
• $a_1 \equiv 1 \pmod 2$，其中 $a_1 = b_0 - b_1 - c_1$；
• $c_2 \equiv 0 \pmod 2$。

这一结果推广并加强了 Key 和 Rodrigues 针对强正则图（SRGs）提出的先前的充分条件，将其适用范围扩展至所有距离正则图。

2. 保持等价性的双射

本文建立了以下两者之间的双射：

• 长度为 $n$ 的二元偶 LCD 码；
• 具有 $\mathbb{F}_2$ 上幂等邻接矩阵的 $n$ 个顶点的简单图。

关键在于，该双射保持等价性：两个码是置换等价的，当且仅当它们对应的图是同构的。这使得编码理论与图理论之间的问题得以相互转化。

3. 组合条件

一个简单图生成二元偶 LCD 码，当且仅当：

• 每个顶点的度数均为偶数；
• 任意两个相邻顶点具有奇数个公共邻居；
• 任意两个非相邻顶点具有偶数个公共邻居。

4. 小规模图的分类

利用该双射和质量公式，本文对所有顶点数不超过 13 且具有幂等邻接矩阵的简单图进行了分类。从 22,213 个长度 $n \le 13$ 的二元 LCD 码中，作者识别出了 1,208 个非同构图，其中包括完全图、完全多部图以及特定的强正则图等已知图族。

结果

特定图族的刻画

一般距离正则图定理为几个著名图族提供了精确的判据：

• 完全图 ($K_n$)：生成 LCD 码当且仅当 $n$ 为奇数。
• 圈图 ($C_n$)：仅 $C_3$（即 $K_3$）生成 LCD 码；$n \ge 4$ 的圈图不生成。
• 汉明图 ($H(n, m)$)：生成 LCD 码当且仅当 $m$ 为奇数。
• 约翰森图 ($J(n, k)$)：生成 LCD 码当且仅当 $n$ 为奇数。
• 格拉斯曼图 ($J_q(n, k)$)：生成 LCD 码当且仅当 $n$ 为奇数且 $q$ 为奇数。若 $q$ 为偶数，则从不生成 LCD 码。

会议图与 Haemers 的观察

本文解决了 Haemers、Peeters 和 van Rijckevorsel 关于会议图（参数为 $(q, (q-1)/2, (q-5)/4, (q-1)/4)$ 的强正则图）的一项计算观察。

• 理论证明：本文证明，会议图生成二元偶 LCD 码当且仅当 $q \equiv 1 \pmod 8$。
• 等价性：本文确认，对于 $q \equiv 1 \pmod 8$ 的非同构会议图，它们生成的码是不等价的。这为“该类中的非同构图产生不同码”这一观察提供了理论解释，该性质此前仅在特定案例（如 $srg(25, 12, 5, 6)$）中通过计算验证。

计算分类

对于 $n \le 13$，分类结果显示：

• 44 个图属于著名图族（6 个完全图，36 个完全多部图，2 个强正则图）。
• 识别出的两个强正则图分别是 9 阶 Paley 图（$srg(9, 4, 1, 2)$）和 Petersen 图的补图（$srg(10, 6, 3, 4)$）。
• 根据 Grassl 的表格，这些特定图生成的码被确认为是最优的。

意义与主张

本文声称通过建立一种既是必要又是充分的结构对应关系，弥合了 LCD 码理论与图理论之间的鸿沟。

• 统一性：该刻画在距离正则性的单一框架下，统一了对完全图、汉明图、约翰森图和格拉斯曼图的处理。
• 理论解释：它首次为“非同构会议图生成不等价码”这一观察提供了理论依据，超越了经验验证。
• 方法论创新：这项工作表明，传统上用于分类码的质量公式，可以被有效地重新用于分类具有特定代数性质（幂等邻接矩阵）的图，从而为图枚举提供了一种新工具。
• 开放问题：本文谦逊地指出，虽然 Paley 图在 $srg(41, 20, 9, 10)$中达到了最大最小距离，但对于所有满足$q \equiv 1 \pmod 8$且$q > 41$ 的会议图，Paley 图是否是唯一的优化器，仍是一个未解决的问题。