度不超过3，直径不超过d的无向图最多有几个点？

hujunhua

7#图有20个顶点，其自同构群和对称度的计算已经超出了我的机器能力。但是，其对称阶则容易观察计算。 7#图的中心五角星是它的最短回路，也是它的唯一的5边回路。因此这5点组成一个对称类。外围五边形的顶点与五角星相邻，而边上的顶点则不邻，故它们各组成一个对称类。所以，7#图的对称阶为{5, 5, 10}. 从7#图中，我得到一个启示，猜想对于更大的 d, 最小对称阶大于1，并能够整除所有较大的对称阶。 d越大，对称阶应该越分散，所以Vmax 应该是一个有较多约数的数。

hujunhua

能否采取一定的去重措施减少输出，并且将输出写入一个txt文件？（如果预估文件较大，为了减小文件，可以不输出固定的饱和点）。 我可以根据输出的txt文件，用M9分析对称性，理出所有不同构的图。 如果从中找到一个奇异分布的对称阶，或许可以直接推翻11#的猜想，并得到另外不同的启示。

KeyTo9_Fans

细数一下，其实也没有想象中的那么多解， 只是因为【距离表】很长，刷屏刷得厉害而已 【sols.txt】是边表，$1$行$1$个图， 图中的$30$条边是用$60$个整数来表示的， 第$1$、$2$个整数表示第$1$条边， 第$3$、$4$个整数表示第$2$条边， 第$5$、$6$个整数表示第$3$条边， 依次类推。 每个图的前$19$条边是固定的，后$11$条边是枚举的。 【sols.txt】一共有$128$行，也就是$128$个解。 sols.txt (19 KB, 下载次数: 7)

2013-5-26 23:01 上传

点击文件名下载附件

##### 根据楼下的指示，改拆顶点$7$和顶点$9$的边，再次枚举，又得$144$解： sols_2.txt (21.38 KB, 下载次数: 3)

2013-5-28 01:26 上传

点击文件名下载附件

hujunhua

13# KeyTo9_Fans 用M9检查的结果，128个解全部同构。 我觉得枚举可能有遗漏。你去掉的两条 3 级边都出自2级顶点9，这个一般性不明显。相反，如果从两个2级顶点上各去掉1条 3 级边，则不失一般性。这有两种情况： 1、从2级顶点7, 9上（7, 9出自2个不同的 1 级顶点）各去掉一条3级边； 2、从2级顶点8, 9上（8, 9出自同一个 1 级顶点3）各去掉一条3级边；这种情况不用考虑，已经包含在第1种情况和你已经得到的128个解中。 虽然遗漏的可能还是同构的图，万一呢？

hujunhua

彼得森图是图论教科书中讲图的同构时常使用的例子，除了标准图（2#图），一般书中用来对比的图都呈三角形，大致如5#图1，反正是比较难看的. 在观察了彼得森图的自同构群（120阶啊，好大哟）后，我得到了两种新的美妙画法。我相信这个应该是咱们坛子的原创。 左图表现它的4阶自同构，右图表现了它的6阶自同构。当然还包括所有的反射自同构（2阶）。 图释： 1、左图中的3, 5，右图中的3, 4, 6都出现了两次。同一个图中重复出现2次的，为同一个点。（这是拓扑中常用的技巧） 2、所以左图中心的圆表示边(3,5). 3、右图中心的1不是6度点，还是3度点，因它的每条边相应地出现了2次

hujunhua

原来，彼得森图不过是坍塌的正十二面体。将正十二面体的对径点标为同一点，就同构于彼得森图。 彼得森图具有单一的对称类（所有的顶点都彼此对称），原来如此！ 15楼的两个图顿时相形见拙，不能赞美了。

hujunhua

13# KeyTo9_Fans 144解同构。鉴定完毕。 我相信6#Fans的枚举没有遗漏，所以现在可以断言：d=3时，Vmax=20，并且满足要求的图是唯一的。

zgg___

呵呵，不错的结论，图形也很优美，很好的呢。 好像和“Degree Diameter Problem”，“Moore graph”啥的相关呢。 在http://en.wikipedia.org/wiki/Moore_graph中有一个open problem：Does a Moore graph with girth 5 and degree 57 exist?曾经在一本组合的书上看到过。呵呵。

hujunhua

我今天搜“给定直径的最大正则图”，也搜到一些资料，表明这是图论中的一个Open problem. Fans好嗅觉！ 3#的上限就是degree=3时的Moore bound。有一个链接中说“In general the largest degree-diameter graphs are much smaller in size than the Moore bound.”（一般情况下最大度径图的阶数远小于Moore bound）.所以， Moore bound只不过是一个简单、粗放的上界。 虽然不是首问，但把degree=3的情况专门提出了，体现了Fans把握问题的分寸。degree=3的情况是最基本的，也是最有吸引力的。

KeyTo9_Fans

当$d=4$时，找到了$1$个$n=32$的解： 0 1 0 2 0 3 1 4 1 5 2 6 2 7 3 8 3 9 4 10 4 11 5 12 5 13 6 14 6 15 7 16 7 17 8 18 8 19 9 20 9 28 10 16 10 21 11 22 11 28 12 15 12 23 13 24 13 25 14 22 14 25 15 26 16 27 17 23 17 28 18 27 18 29 19 23 19 30 20 24 20 31 21 30 21 31 22 29 24 27 25 30 26 29 26 31 但不知道最优解有几个点。