同谱图

同谱图，也称为等谱图，是共享相同图谱的图。最小的等谱图对是图的并和星图，如上图所示，它们都具有图谱（Skiena 1990，第 85 页）。第一个例子由 Collatz 和 Sinogowitz (1957) 发现（Biggs 1993，第 12 页）。Cvetkovic等人 (1998, pp. 156-161) 和 Rücker等人 (2002) 给出了许多例子。最小的同谱图对是图的并和星图，如上图所示，它们都具有图谱（Skiena 1990，第 85 页）。

下表总结了一些著名的命名同谱图。

	同谱图
12	6-反棱柱图, 四次顶点传递图 Qt19
16	霍夫曼图, 超立方体图
16	(4,4)-车图, Shrikhande 图
25	25-Paulus 图
26	26-Paulus 图
28	Chang 图, 8-三角形图
70	哈里斯图, 哈里斯-王图

确定哪些图是由其谱唯一确定的通常是一个非常困难的问题。只有一小部分图已知是由其谱唯一确定的，但几乎所有图都可能具有此属性（van Dam 和 Haemers 2003，Haemers 2016），这种断言有时被称为 Haemers 猜想。

Brouwer 和 Spence (2009) 确定了节点数达到的个节点的同谱简单图的数量，给出的结果为 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, 215331676, 3106757248, ... (OEIS A006608) 对于 , 2, .... 等等。同谱简单图对（不包括作为三元组等一部分的对）的数量为 0, 0, 0, 0, 1, 5, 52, 771, 21025, ... (OEIS A099881)。类似地，同谱图三元组（不包括作为四元组等一部分的三元组）的数量为 0, 0, 0, 0, 0, 0, 2, 52, 2015, ... (OEIS A099882)。

另请参阅

由谱确定, 图的特征值, 图谱, 霍夫曼图, 同谱流形, Shrikhande 图

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Biggs, N. L. 代数图论，第二版 Cambridge, England: Cambridge University Press, p. 12, 1993.Brouwer, A. E. and Spence, E. "12 个顶点的同谱图。" Elect. J. Combin., Vol. 16, No. 1, 2009. https://doi.org/10.37236/258.Collatz, L. and Sinogowitz, U. "有限图的谱。" Abh. Math. Sem. Univ. Hamburg 21, 63-77, 1957.Cvetković, D. M.; Doob, M.; and Sachs, H. 图谱：理论与应用，第三版修订增补版 New York: Wiley, 1998.Godsil, C. D. and McKay, B. D. "构造同谱图。" Aeq. Math. 25, 257-268, 1982.Haemers, W. H. "几乎所有图都由其谱唯一确定吗？" Not. S. Afr. Math. Soc. 47, 42-45, 2016.Haemers, W. H. and Spence, E. "与距离正则图同谱的图。" Linear Multilin. Alg. 39, 91-107, 1995.Rücker, C.; Rücker, G.; and Meringer, M. "探索基于图不变性和谱的（子）结构判别的局限性。" J. Chem. Inf. Comp. Sci. 42, 640-650, 2002.Skiena, S. 离散数学实现：组合数学和图论与 Mathematica。 Reading, MA: Addison-Wesley, p. 85, 1990.Sloane, N. J. A. 序列 A006608, A099881, 和 A099882在“整数序列在线百科全书”中。van Dam, E. R. and Haemers, W. H. "一些距离正则图的谱特征。" J. Algebraic Combin. 15, 189-202, 2003.

在 Wolfram|Alpha 中被引用

同谱图

请引用为

Weisstein, Eric W. "同谱图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/CospectralGraphs.html