主題
Search

同譜圖


IsospectralGraphs

同譜圖,也稱為等譜圖,是共享相同圖譜的圖。最小的等譜圖對是圖的並 C_4 union K_1星圖 S_5,如上圖所示,它們都具有圖譜 (-2)0^32(Skiena 1990,第 85 頁)。第一個例子由 Collatz 和 Sinogowitz (1957) 發現(Biggs 1993,第 12 頁)。Cvetkovic等人 (1998, pp. 156-161) 和 Rücker等人 (2002) 給出了許多例子。最小的同譜圖對是圖的並 C_4 union K_1星圖 S_5,如上圖所示,它們都具有圖譜 (-2)0^32(Skiena 1990,第 85 頁)。

下表總結了一些著名的命名同譜圖。

確定哪些圖是由其譜唯一確定的通常是一個非常困難的問題。只有一小部分圖已知是由其譜唯一確定的,但幾乎所有圖都可能具有此屬性(van Dam 和 Haemers 2003,Haemers 2016),這種斷言有時被稱為 Haemers 猜想

Brouwer 和 Spence (2009) 確定了節點數達到 n=12n 個節點的同譜簡單圖的數量,給出的結果為 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, 215331676, 3106757248, ... (OEIS A006608) 對於 n=1, 2, .... 等等。同譜簡單圖對(不包括作為三元組等一部分的對)的數量為 0, 0, 0, 0, 1, 5, 52, 771, 21025, ... (OEIS A099881)。類似地,同譜圖三元組(不包括作為四元組等一部分的三元組)的數量為 0, 0, 0, 0, 0, 0, 2, 52, 2015, ... (OEIS A099882)。


另請參閱

由譜確定, 圖的特徵值, 圖譜, 霍夫曼圖, 同譜流形, Shrikhande 圖

使用 探索

參考文獻

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.

在 中被引用

同譜圖

請引用為

Weisstein, Eric W. "同譜圖。" 來自 —— 資源。 https://mathworld.tw/CospectralGraphs.html

主題分類