主題
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.tw/DeterminedbySpectrum.html

學科分類