2级切换方法用于构造同谱图

《Linear Algebra and its Applications》：Switching methods of level 2 for the construction of cospectral graphs

　　

摘要
切换方法是一种图操作，其结果是产生同谱图（具有相同谱的图）。Wang和Xu（2010）[31]的研究表明，大多数具有同谱补图的同谱图可以通过2级的正则正交矩阵（regular orthogonal matrices of level 2）构造，这与Haemers猜想（Haemers' conjecture）具有相关性。研究人员提出了两种新的切换方法，并对现有的2级切换操作进行了若干组合与几何重述。研究人员还引入了可约性（reducibility）的概念，并利用该概念对所有对应于具有一个非平凡不可分解块（indecomposable block）的2级正则正交矩阵共轭的不可约切换方法进行了分类，涵盖切换集大小至12的情形，从而扩展了先前的研究结果。

论文解读

**一、研究背景与问题**

谱图理论中的一个重要问题是理解哪些图由其（邻接矩阵的）谱在同构意义下唯一确定。这一问题的研究动机源于对实用图同构测试（graph isomorphism test）的追求。该领域一个主要的未解猜想是由Haemers提出的，即“几乎所有图都由其谱唯一确定”。Brouwer和Spence通过枚举所有至多12个顶点的图（扩展了Godsil和McKay以及Haemers和Spence的工作）为该猜想提供了计算证据，并观察到在10至12个顶点之间，同谱对（cospectral mates，即具有相同谱但非同构的图）的比例有所下降。另一方面，Haemers和Spence建立了同谱对数量的渐近下界，其关键工具是切换（switching）的概念。

切换方法是对图的一种操作，其结果产生具有相同谱的图。此类方法要求图具有一种特殊结构，称为切换集（switching set）。Godsil-McKay（GM）切换是文献中最古老且最高产的切换方法，但近年来出现了新的切换方法，最著名的是Abiad和Haemers引入的切换方法以及Wang-Qiu-Hu（WQH）切换。构造同谱对有多种用途：证明某个图类不由其谱确定，从而为Haemers猜想提供新见解；展示图的哪些性质不能从谱中推导出来；或构造新的强正则图和距离正则图。

2级切换方法（level 2 switching methods）的动机源于Wang和Xu的结果，该结果表明大多数R-同谱图（R-cospectral graphs，即具有同谱补图的同谱图）可以用2级的正则正交矩阵构造。基于这一动机，研究人员进一步推进了这条研究路线，扩展了先前的研究结果。具体而言，研究人员提出了两种新的2级切换方法来构造R-同谱图，并特别关注具有小切换集的切换方法，因为它们似乎对构造同谱图最为有效。研究人员引入了不可约切换方法（irreducible switching methods）的概念，并对所有具有一个非平凡不可分解块的2级不可约切换方法给出了完整描述，涵盖切换集大小为6、8、10和12的情形。

Abiad和Haemers引入的2级切换方法以代数方式描述，难以直接应用。Mao、Wang、Liu和Qiu对此类方法进行了初步的组合描述。在此基础上，研究人员给出了六顶点AH切换（Six vertex AH-switching）的组合描述，并将该结果扩展到切换集大小为8、10和12的情形。类似地，研究人员分别提出了七顶点AH切换（Seven vertex AH-switching）和八顶点AH切换（Eight vertex AH-switching）的几何与组合解释。利用七顶点AH切换的几何解释，研究人员获得了关于2-Kneser图已知同谱性结果的更短、更直观的证明，这是2级切换方法在图论中的首次应用。

**二、主要技术方法**

本研究采用的主要技术方法包括：第一，基于Chan、Rodger和Seberry对权重为4的称重矩阵的分类，以及Wang和Xu的重述，对2级不可分解正则正交矩阵进行分类（见定理3）；第二，通过分析正则正交矩阵R作用下的列向量集合V_R和邻接矩阵集合B_R，来确定切换操作成立的条件；第三，引入可约性（reducibility）概念，将切换方法分解为更小的切换方法的序列；第四，利用计算机辅助（Sagemath代码见附录A）对切换集大小至12的所有不可约切换方法进行分类验证。所有分类结果均在组合和几何层面进行重述。

**三、研究结果**

**3.1 两种新的2级切换方法**

定理7提出了一种新的切换方法，其对应的矩阵为定理3(ii)中的2m×2m正则正交矩阵R_2m=?circulant(J,O,…,O,Y)，其中m为奇数且m≥3。该方法要求顶点划分为{C₁,…,C_m,D}，每个C_i包含2个顶点，D中每个顶点在C₁,…,C_m中的邻居数模2相同，且C_i∪C_j上的诱导子图满足特定条件（即每个块B_ij为O、I、N、N^T或它们的补图，其中N=[[0,0],[1,1]]）。操作方式为：将D中恰好在每个C_i中有一个邻居w的顶点v，将边{v,w}替换为{v,π(w)}（π为循环左移置换），并将C_i∪C_j上的诱导子图替换为C_i+1∪C_j+1上的原诱导子图（若ji+1∪C_j上的原诱导子图（若j=i+(m-1)/2）。定理8提出了第二种新的切换方法，适用于m≥5的情形，其操作规则与定理7类似但块间替换模式不同：将C_i∪C_i+1上的诱导子图替换为C_i∪C_i+2上的原诱导子图，将C_i∪C_i+2上的诱导子图替换为C_i+1∪C_i+2上的原诱导子图。推论9给出了m=5时的三种具体情形。

**3.2 可约性与Sun图切换的不可约性**

定义10引入了可约性（reducibility）的概念：若一个2级切换方法可以通过一系列更小的切换方法（即来自最大不可分解块更小的矩阵的切换方法）获得，则称其为可约的；否则为不可约的。引理12证明了若B关于R_2m可约，则它必来自形如diag(R_2m1,…,R_2md)的矩阵序列，且更小方法的切换集是原切换集C_i的并集。定理13证明了Sun图切换（定理5）对所有奇数m≥3都是不可约的，证明采用反证法，利用引理12将可约性归结为更小切换方法的乘积，然后通过分析块结构得出矛盾。

**3.3 不可约切换方法的分类**

对于来自无穷族定理3(ii)的矩阵，当m=3时（六顶点AH切换），定理20给出了唯一不可约情形：C₁∪C₂∪C₃上的诱导子图为K_3,3（完全二部图），操作方式为将边替换为π(w)并替换诱导子图。引理19给出了可约性的充要条件：当且仅当C₁∪C₂、C₂∪C₃或C₁∪C₃中至少一个诱导子图是正则的，且其余两个顶点与其有偶数条邻接边。

对于m=4（八顶点AH切换，来自无穷族），定理21通过计算机验证证明了B_R8中的所有矩阵都是可约的，这令人惊讶。

对于m=5（十顶点切换），定理22通过计算机验证证明了B_R10恰好有三个不可约矩阵（在补图和共轭意义下），它们对应于推论9的三种切换方法。

对于m=6（十二顶点切换），表1列出了18个不可约邻接矩阵B₁,…,B₁₈∈B_R12，定理23给出了其组合表述：要求C₁∪…∪C₆上的邻接矩阵为表1中的18个矩阵之一（允许任何2×2块及其转置被其补图替换），操作方式为将边替换为π(w)并将诱导子图替换为R₁₂^TBR₁₂。

**3.4 Fano切换（七顶点AH切换）**

定理25给出了Fano切换的不可约情形。其几何解释基于Fano平面PG(2,2)：将C={v₁,…,v₇}中的点视为Fano平面的点，线?_i={v_i,v_i+1,v_i+2}（下标模7）构成Fano平面的7条线。C上的诱导子图有两种不可约情形：空图（B=O）或K₇（完全图）。D中每个顶点要么与C中所有顶点相邻、要么与C中无顶点相邻、要么与一条线上的三个顶点相邻、要么与不在一条线上的四个顶点相邻。操作方式为：对于与线?_i的三个顶点相邻（或不相邻）的顶点v，使其与O_i={v_i+2,v_i+4,v_i+5}的三个顶点相邻（或不相邻）。定理27利用Fano切换给出了2-Kneser图K₂(n,k)不由其谱确定的更短证明，该结果最初由Abiad等人用GM切换证明。

**3.5 Cube切换（八顶点AH切换，零星矩阵）**

定理31给出了Cube切换的完整描述，其几何解释基于三维仿射空间AG(3,2)（即立方体的8个顶点）。引理30证明了v∈V_R当且仅当v=0、v=1或v是AG(3,2)中一个仿射平面的特征向量（即立方体的面、连接两条相对边的平面或四个不相邻顶点的集合）。操作方式为：面映射到其在置换π下的像，连接相对边的平面映射到其补集（作为顶点集），四个不相邻顶点的集合保持不变。定理29通过计算机验证证明了所有B_Rcube中的矩阵都是可约的。表2列出了40个不可约矩阵B₆,…,B₄₀（连同B₁=O至B₅），给出了Cube切换的完整代数描述。

**四、讨论与结论**

本研究提出了两种新的2级切换方法（定理7和定理8），用于构造R-同谱图，并完成了所有具有一个非平凡不可分解块且切换集大小至多12的2级不可约切换方法的分类，扩展了先前的结果。这些方法包括：GM切换（4顶点）、六顶点AH切换（6顶点）、Fano切换（7顶点）、十顶点切换（10顶点）和十二顶点切换（12顶点）。此外，研究人员还提供了Sun图切换（或MWLQ切换）、六顶点AH切换的更直观的组合解释，以及七顶点AH切换（Fano切换）和零星八顶点AH切换（Cube切换）的几何描述。利用Fano切换的几何解释，研究人员推导了2-Kneser图不由其谱确定的更短证明。

作为未来工作，研究人员提出以下开放问题：研究新引入的2级方法在构造新的强正则图等方面的更多应用；关于定理13，定理7和定理8中的新无穷族是否不可约仍然悬而未决；研究来自具有多个非平凡不可分解块的矩阵的2级切换方法仍是一个开放问题；将第6节的分类扩展到来自具有多个非平凡不可分解块的矩阵的方法，此类扩展还应包括对这些方法的可约性定义的推广。