主題
Search

共形剛性圖


L_w 為加權拉普拉斯矩陣,定義在一個具有 簡單 連通圖 上,該圖有 n 個頂點,邊集E,邊權重為 w_(ij),定義如下:

 (L_w)_(ij)={-w_(ij)   for (i,j) in E; sum_(j∼i)w_(ij)   for i=j; 0   otherwise,
(1)

其中 j∼i 表示 (i,j) in E。令 L_w 具有特徵值:

 0=lambda_1(w)<lambda_2(w)<=...<=lambda_n(w),
(2)

1 為長度為 n 的向量,其所有元素均為 1。Steinerberger 和 Thomas (2024) 將一個圖稱為共形剛性圖,如果其加權拉普拉斯特徵值滿足:

 lambda_2(w)<=lambda_2(1)<=lambda_n(1)<=lambda_n(w^')
(3)

對於所有非負且歸一化的邊權重 w_(ij)w_(ij)^',滿足:

 sum_((i,j) in E)w_(ij)=sum_((i,j) in E)w_(ij)^'=|E|,
(4)

其中 |E|G邊數

共形剛性反映了一個圖中非凡的對稱性 (Steinerberger 和 Thomas 2024)。

所有連通的邊傳遞圖距離正則圖都是共形剛性的 (Steinerberger 和 Thomas 2024)。 由於連通的距離正則圖強正則圖,因此連通的強正則圖也是共形剛性的。

在 10 個或更少頂點上,沒有既是邊傳遞圖又是距離正則圖的共形剛性圖 (E. Weisstein, 2024 年 3 月 1 日)。 已知的最小的既不是邊傳遞圖也不是距離正則圖的共形剛性圖是 16 個頂點的 Hoffman 圖 (Steinerberger 和 Thomas 2024)。 下表擴充套件了 Steinerberger 和 Thomas (2024) 的結果,列出了所有 13 個已知的此類特殊共形剛性圖 (E. Weisstein, 2024 年 2 月 23 日)。

|V|非邊傳遞、非距離正則、共形剛性圖
16Hoffman 圖
18迴圈圖 Ci_18(1,5)
20最小三次交叉數圖 CNG6B
20565-Haar 圖
20(10, 3)-關聯圖 3
20(10, 3)-關聯圖 4
2020-非 Cayley 頂點傳遞圖 10
2424-Klein 圖的距離-2 圖
2424-非 Cayley 頂點傳遞圖 23
40(20, 8)-手風琴圖
48(0, 2)-二部圖 (7, 1)
48(0, 2)-二部圖 (7, 2)
120120-Klein 圖

一些 Cayley 圖 是共形剛性的,而另一些則不是。 Steinerberger 和 Thomas (2024) 為 Cayley 圖成為共形剛性圖提供了充分條件。

迴圈圖 Ci_n(1,2) 對於 n>=7 不是 共形剛性的 (Steinerberger 和 Thomas 2024),這意味著反稜柱圖 (八面體圖除外) 也不是共形剛性的。


另請參閱

拉普拉斯矩陣, 加權圖

使用 探索

參考文獻

Steinerberger, S. 和 Thomas, R. R. "共形剛性圖。" 2024 年 2 月 19 日。 https://arxiv.org/abs/2402.11758.

引用為

Weisstein, Eric W. "共形剛性圖。" 來自 Web 資源。 https://mathworld.tw/ConformallyRigidGraph.html

主題分類