主题
Search

由谱确定


GraphSpectrum

两个非同构图可以共享相同的 图谱,即,具有相同邻接矩阵的特征值。这样的图被称为 同谱图。例如,图的并 C_4 union K_1星图 S_5,如上图所示,都具有谱 (-2,0,0,0,2) (Skiena 1990, p. 85)。这是最小的一对同谱简单图。

一个不与任何其他图同谱的图被称为“由谱确定”,或简称 DS。确定哪些图是由其谱唯一确定的,一般来说是一个非常困难的问题。只有一小部分图已知是如此确定的,但正如 van Dam 和 Haemers 所推测的那样 (van Dam and Haemers 2002, Haemers 2016),几乎所有 图都可能具有此属性。这种断言有时被称为 Haemers 猜想

简单图和 DS 图的数量,以及 n=1 到 12 个顶点的 DS 图的比例可以总结在下表中 (Wang and Wang 2024),该表来源于 Brouwer 和 Spence (2009) 的结果。

n# 图的数量# DS 图的数量DS 图的比例
OEISA000088A178925
111100%
222100%
344100%
41111100%
5343294.1%
615614693.6%
7104493489.5%
8123461062486.1%
927466822362981.4%
1012005168944456278.7%
11101899786480366618878.9%
1216509117259213402360011181.2%

Wolfram 语言 中,已知由其谱确定的图被标识为GraphData["DeterminedBySpectrum"].

n=1, 2, ... 个节点上由谱确定的简单图的数量是 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925),而相应不由谱确定的数量是 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, ... (OEIS A06608)。

已知由其谱唯一确定的图包括 完全图 K_n、正则完全二分图 K_(n,n)圈图、三角形图,对于 n!=8,以及 车图 L_k,对于 k!=4 (Haemers 2006)。此外,Coxeter 图Biggs-Smith 图、广义八边形的共线图,阶数为 (2,1)(3,1)(4,1)广义十二边形 (2,1)M22 图,以及双重截断二元 Golay 码 和扩展三元 Golay 码 的陪集图,都由其谱确定 (van Dam and Haemers 2003b)。

由其谱确定的距离正则图的补图也由其谱确定 (van Dam and Haemers 2003b)。强正则由谱确定图的多个副本的 不相交并 也由谱确定 (van Dam and Haemers 2003b)。

Ci_(5k)(1,4,6,9,11,14,...,|_5k/2_|) 给出了由谱确定的图的无限族,它是 C_5 tensor J_k,其中 J_kk×k 单位矩阵 tensor 表示邻接矩阵的 Kronecker 积 (van Dam and Haemers 2003b),而 1, 4, 6, 9, 11, ... (OEIS A047209) 是正整数序列,它们与 1 和 4 (mod 5) 同余。

不由其谱确定的图包括 车图 L_4Shrikhande 图超立方体图 Q_4Hoffman 图三角形图 T_8Chang 图,以及 25- 和 26-Paulus 图


另请参阅

Chang 图, 同谱图, 图同构, 图谱, Hoffman 图, Shrikhande 图

使用 探索

参考文献

Brouwer, A. E. and Spence, E. "Cospectral Graphs on 12 Vertices." Elect. J. Combin., Vol. 16, No. 1, 2009. https://doi.org/10.37236/258.Haemers, W. H. "Spectral Characterization of Graphs." In IPM Combinatorics II: Design Theory, Graph Theory, and Computational Methods. April 22-27, 2006, IPM, Tehran. http://www.ipm.ac.ir/combinatoricsII/abstracts/Haemers1.pdf.Haemers, W. H. "Are Almost All Graphs Determined by Their Spectrum?" Not. S. Afr. Math. Soc. 47, 42-45, 2016.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences AA06608/M1981, A047209, and A178925 in "The On-Line Encyclopedia of Integer Sequences."van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003a.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003b.Wang, W. and Wang, W. "Haemers' Conjecture: An Algorithmic Perspective." Experimental Math., 10 Apr 2024.

请引用为

Weisstein, Eric W. "由谱确定." 来自 Web 资源。 https://mathworld.net.cn/DeterminedbySpectrum.html

学科分类