单圈图的度相似检验

最近一段时间我在用SageMath检验图的度相似问题,为了安装和使用SageMath还产出了副产物 Sage安装指南.但坏消息是并没有检验出来什么结果.这个问题是希望能够回答Degree-Similar Graphs中的Problem 1,即是否存在不同构但度相似单圈图,但坏消息是在检验下对于20点及以下的单圈图都不成立.

图$G_1, G_2$度相似(degree similar)是指存在可逆矩阵$M$使得邻接矩阵$A_1=A(G_1), A_2=A(G_2)$与度数矩阵$D_1=D(G_1), D_2=D(G_2)$同时相似,即

\[M^{-1}A_1M=A_2, M^{-1}D_1M=D_2\]

因此我们有一系列必要条件:若两个图度相似,则它们不止顶点数相同,且其度数序列相等,谱半径相同(实际上,邻接矩阵相同),围长相同(需要一些分析)且(无符号)Laplace矩阵相似.当然可以导出更多,但最本质也是最难以计算的(复杂度高达$O(n^3)$)就是一系列图的特征多项式.在计算过程中发现非负矩阵的谱半径一般不会同样达到$O(n^3)$,而可以通过Perron-Frobenius定理进行$k$次迭代,因此大概在$O(k\cdot n^2)$的水平.

我在Grok的帮助下写了Sage代码 Unicyclic_main.ipynb用于生成并不断分类$n$点$(5\leq n\leq 20)$的单圈图.首先用nauty_geng不断生成,再依次按照度数序列,围长,邻接矩阵的谱半径以及Laplace矩阵的特征多项式(或谱)来分类,每次分类剔除只有一个图的分类(因为显然不可能与其它图度相似了),最后得到一个包含Graph6格式的json文件,其中每个列表是上述属性均相同的图.此时可再进行进一步验证是否度相似.

这里的关键问题在于,单圈图的个数在A001429中记录,$n\leq 20$时共有大约三千万个单圈图.生成,计算和储存它们都要消耗大量算力和内存,因此我在计算过程中用了一些简单的批处理和并行运算技巧(因为我也不会,我也是初学者)且在计算过程中不断输出以Graph6格式记录的已分类图,这可以极大压缩储存空间.但哪怕如此,$n=20$时最后的计算结果也有64KB,即一千多个图.

在得到预分类的图后,将其导入Mathematica程序度相似计算.nb并用符号计算验证其是否度相似.这并不困难,但总之坏消息是这总是不存在的.