主题
Search

极大优美图


极大优美图是一个优美图,它在所有具有相同顶点数的图中具有最大可能数量的优美标号

MaximallyGracefulGraphs

对于各种类型的极大优美图,在 n=1, 2, ... 个顶点上,其根本不同的优美标号的数量总结在下表中,并在上面针对所有简单图进行了说明。

OEIS计数类型
A3793951, 1, 1, 5, 26, 126, 680, 3876, ...简单图
A3398921, 1, 1, 5, 26, 126, 680, 3778, ...没有孤立点的简单图
1, 1, 1, 5, 26, 126, 680, 3778, ...简单 连通图
MaximallyGracefulConnectedGraph8

Knuth (2024) 仅在不包含孤立点的图中考虑了极大优美图。这些计数与所有连通图和所有简单图在顶点数 n=7 以内时相同,但在 n=8 时有所不同,8 顶点极大优美连通(且无孤立点)图具有 3778 个(而不是 3876 个)根本不同的优美标号。上面说明了这个图。它也很重要,因为它也是具有最大数量(80 个)平面嵌入的 8 顶点图。

极大优美树也被考虑。


另请参阅

优美图, 优美标号, 极大优美树

使用 Wolfram|Alpha 探索

参考文献

Knuth, D. E. 问题 97,§7.2.2.3,出自计算机程序设计艺术,卷 4B:组合算法,第二部分。 New York: Addison-Wesley, 2022.A339892A379395 在“整数序列在线百科全书”中。

请引用本文为

Weisstein, Eric W. "极大优美图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/MaximallyGracefulGraph.html

主题分类