两个非同构图可以共享相同的 图谱,即,具有相同邻接矩阵的特征值。这样的图被称为 同谱图。例如,图的并 和 星图
,如上图所示,都具有谱
(Skiena 1990, p. 85)。这是最小的一对同谱简单图。
一个不与任何其他图同谱的图被称为“由谱确定”,或简称 DS。确定哪些图是由其谱唯一确定的,一般来说是一个非常困难的问题。只有一小部分图已知是如此确定的,但正如 van Dam 和 Haemers 所推测的那样 (van Dam and Haemers 2002, Haemers 2016),几乎所有 图都可能具有此属性。这种断言有时被称为 Haemers 猜想。
简单图和 DS 图的数量,以及 到 12 个顶点的 DS 图的比例可以总结在下表中 (Wang and Wang 2024),该表来源于 Brouwer 和 Spence (2009) 的结果。
# 图的数量 | # DS 图的数量 | DS 图的比例 | |
OEIS | A000088 | A178925 | |
1 | 1 | 1 | 100% |
2 | 2 | 2 | 100% |
3 | 4 | 4 | 100% |
4 | 11 | 11 | 100% |
5 | 34 | 32 | 94.1% |
6 | 156 | 146 | 93.6% |
7 | 1044 | 934 | 89.5% |
8 | 12346 | 10624 | 86.1% |
9 | 274668 | 223629 | 81.4% |
10 | 12005168 | 9444562 | 78.7% |
11 | 1018997864 | 803666188 | 78.9% |
12 | 165091172592 | 134023600111 | 81.2% |
在 Wolfram 语言 中,已知由其谱确定的图被标识为GraphData["DeterminedBySpectrum"].
在 , 2, ... 个节点上由谱确定的简单图的数量是 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925),而相应不由谱确定的数量是 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, ... (OEIS A06608)。
已知由其谱唯一确定的图包括 完全图 、正则完全二分图
、圈图、三角形图,对于
,以及 车图
,对于
(Haemers 2006)。此外,Coxeter 图、Biggs-Smith 图、广义八边形的共线图,阶数为
、
和
,广义十二边形
、M22 图,以及双重截断二元 Golay 码 和扩展三元 Golay 码 的陪集图,都由其谱确定 (van Dam and Haemers 2003b)。
由其谱确定的距离正则图的补图也由其谱确定 (van Dam and Haemers 2003b)。强正则由谱确定图的多个副本的 不相交并 也由谱确定 (van Dam and Haemers 2003b)。
由 给出了由谱确定的图的无限族,它是
,其中
是
单位矩阵,
表示邻接矩阵的 Kronecker 积 (van Dam and Haemers 2003b),而 1, 4, 6, 9, 11, ... (OEIS A047209) 是正整数序列,它们与 1 和 4 (mod 5) 同余。
不由其谱确定的图包括 车图 和 Shrikhande 图、超立方体图
和 Hoffman 图、三角形图
和 Chang 图,以及 25- 和 26-Paulus 图。