主題
Search

距離正則圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

一個 連通圖 G 是距離正則的，如果對於 x 和 y 在 G 中的任意頂點，以及任意整數 i,j=0, 1, ...d (其中 d 是 圖直徑)，從 x 距離為 i 且從 y 距離為 j 的頂點數，僅取決於 i, j, 以及 x 和 y 之間的 圖距離，而與 x 和 y 的選擇無關。

特別地，距離正則圖是一個圖，其中存在整數 b_i,c_i,i=0,...,d，使得對於任意兩個頂點 x,y in G 和距離 i=d(x,y)，恰好有 c_i 個 y in G_(i-1)(x) 的鄰居和 b_i 個 y in G_(i+1)(x) 的鄰居，其中 G_i(x) 是頂點集合 y 在 G 中且 d(x,y)=i (Brouwer et al. 1989, p. 434)。表徵距離正則圖的整數陣列被稱為其相交陣列。

圖 G 的距離正則性可以在GRAPE包中檢查，在GAP中使用函式IsDistanceRegular(G).

一個 非連通圖 是距離正則的 當且僅當 它是 同譜 距離正則圖的不交併。

Fiol 和 Garriga (1997) 的一個深刻定理指出，一個圖是距離正則的 當且僅當 對於每個頂點，距離為 d (其中 d+1 是不同圖特徵值的數量) 的頂點數等於譜的表示式 (van Dam 和 Haemers 2003)。

距離正則圖的型別包括 完全圖 K_n, 完全二部圖 K_(n,n), 完全三部圖 K_(n,n,n), 圈圖 C_n (Brouwer et al. 1989, p. 1), 空圖 K^__n (平凡地), Hadamard 圖 (Brouwer et al. 1989, p. 19), 超立方體圖 Q_n (Biggs 1993, p. 161), Kneser 圖 K(n,2), 梯子階圖 nP_2 (平凡地), 奇圖 O_n (Biggs 1993, p. 161), 和 柏拉圖圖 (Brouwer et al. 1989, p. 1)。

一個 圖直徑 為 d=2 的距離正則圖是一個 強正則圖 (Biggs 1993, p. 159)，且 連通 距離正則圖是 共形剛性 的 (Steinerberger 和 Thomas 2024)。

每個 距離傳遞圖 都是距離正則的，但反之不一定成立，正如 Adel'son-Vel'skii et al. (1969; Brouwer et al. 1989, p. 136) 首次表明的那樣。最小的非 距離傳遞 的距離正則圖是 16 個節點的 Shrikhande 圖 (Brouwer et al. 1989, p. 136)。

DistanceRegularCubic

所有 三次 距離正則圖都是已知的 (Biggs et al. 1986; Brouwer et al. 1989, p. 221; Royle)，如上圖所示，並在下表中總結。

n圖相交陣列
4四面體圖{3;1}
6效用圖{3,2;1,3}
8立方圖{3,2,1;1,2,3}
10Petersen 圖{3,2;1,1}
14Heawood 圖{3,2,2;1,1,3}
18Pappus 圖{3,2,2,1;1,1,2,3}
20Desargues 圖{3,2,2,1,1;1,1,2,2,3}
20十二面體圖{3,2,1,1,1;1,1,1,2,3}
28Coxeter 圖{3,2,2,1;1,1,1,2}
30Tutte 8-籠{3,2,2,2;1,1,1,3}
90Foster 圖{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
102Biggs-Smith 圖{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
126Tutte 12-籠{3,2,2,2,2,2;1,1,1,1,1,3}

所有 四次 距離正則圖都是已知的 (Brouwer 和 Koolen 1999)，除了列表中有一個圖 (階數為 3 的廣義六邊形) 尚未被證實由其相交陣列唯一確定 (Koolen et al. 2023)。特別是，任何 4 價距離正則圖都具有以下列出的 17 個相交陣列之一 (因此是所描述的 16 個圖之一，或者是階數為 3 的廣義六邊形的點-線關聯圖)

編號vd圖相交陣列譜
1.51五胞體圖 K_5{4;1}4^1(−1)4
2.62八面體圖 K_(3×2){4,1;1,4}4^10^3(-2)^2
3.82完全二部圖 K_(4,4){4,3;1,4}+/-4^10^6
4.92廣義四邊形 GQ(2,1){4,2;1,2}4^11^4(-2)^4
5.103冠圖 K_2 square K_5^_{4,3,1;1,3,4}+/-(4^11^4)
6.143PG(2,2) Qt31 的非關聯圖{4,3,2;1,2,4}+/-(4^1sqrt(2)^6)
7.153線圖 of the Petersen 圖 L(P){4,2,1;1,1,4}4^12^5(-1)^4(-2)^5
8.164超立方體圖 Q_4{4,3,2,1;1,2,3,4}+/-(4^12^4)0^6
9.213廣義六邊形 GH(2,1){4,2,2;1,1,2}4^1(1+/-sqrt(2))^6(-2)^8
10.263PG(2,3) 的關聯圖{4,3,3;1,1,4}+/-(4^1sqrt(3)^(12))
11.324AG(4,4) 減去平行類 的關聯圖{4,3,3,1;1,1,3,4}+/-(4^12^(12))0^6
12.353奇圖 O_4{4,3,3;1,1,2}4^12^(14)(-1)^(14)(-3)^6
13.454廣義八邊形 GO(2,1){4,2,2,2;1,1,1,2}4^13^91^(10)(-1)^9(-2)^(16)
14.707Danzer 圖{4,3,3,2,2,1,1;1,1,2,2,3,3,4}+/-(4^13^62^(14)1^(14))
15.804(4,8)-籠圖{4,3,3,3;1,1,1,4}+/-(4^1sqrt(6)^(24))0^(30)
16.1896廣義十二邊形 GD(2,1){4,2,2,2,2,2;1,1,1,1,1,2}4^1(1+/-sqrt(6))^(21)(1+/-sqrt(2))^(27)1^(28)(-2)^(64)
17.7286(4,12)-籠圖{4,3,3,3,3,3;1,1,1,1,1,4}+/-(4^13^(104)sqrt(3)^(168))0^(182)

Koolen 等人 (2023) 枚舉了 18 種非幾何 距離正則圖的例子，這些圖的直徑至少為 3，且最小圖特徵值至少為 -3，如下表所示。

例子圖相交陣列
(a)奇圖 O_4{3,3,3;1,1,2}
(b)Sylvester 圖{5,4,2;1,1,4}
(c)Hoffman-Singleton 圖 的第二個子構成圖{6,5,1;1,1,6}
(d)Perkel 圖{6,5,2;1,1,3}
(e)完全圖 K_9 的辛 7-覆蓋{8,6,1;1,1,8}
(f)Coxeter 圖{3,2,2,1;1,1,1,2}
(g)十二面體圖{3,2,1,1,1;1,1,1,2,3}
(h)Biggs-Smith 圖{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
(i)Wells 圖{5,4,1,1;1,1,4,5}
(j)二十面體圖{5,2,1;1,2,5}
(k)Hall 圖{10,6,4;1,2,5}
(l)半立方體圖 Q_6/2{15,6,1;1,6,15}
(m)Gosset 圖{27,10,1;1,10,27}
(n)半立方體圖 Q_7/2{21,10,3;1,6,15}
(o)24-Klein 圖{7,4,1;1,2,7}
(p)恰好兩個距離正則圖{9,6,1;1,2,9}
(q)多於一個距離正則圖{15,10,1;1,2,15}
(r)推定的距離正則圖{18,12,1;1,2,18}

請注意，奇 n-圈圖，其中 n>3 (滿足所有給定條件) 顯然被默默地省略了。

下表總結了一些已知的距離正則圖，排除了一些已命名的族。

n圖相交陣列
5五胞體圖{4;1}
6八面體圖{4,1;1,4}
816-胞圖{6,1;1,6}
9廣義四邊形 (2,1){4,2;1,2}
12二十面體圖{5,2,1;1,2,5}
14四次頂點傳遞圖 Qt31{4,3,2;1,2,4}
15廣義四邊形 (2,2){6,4;1,3}
15四次頂點傳遞圖 Qt39{4,2,1;1,1,4}
16Clebsch 圖{5,4;1,2}
16Shrikhande 圖{6,3;1,2}
16超方形圖{4,3,2,1;1,2,3,4}
21(7,2)-Kneser 圖{10,6;1,6}
21廣義六邊形 (2,1){4,2,2;1,1,2}
22(11,5,2)-關聯圖{5,4,3;1,2,5}
22(11,6,3)-關聯圖{6,5,3;1,3,6}
24Klein 圖{7,4,1;1,2,7}
2525-Paulus 圖{12,6;1,6}
26(13,9,6)-關聯圖{9,8,3;1,6,9}
2626-Paulus 圖{10,6;1,4}
26(29,14,6,7)-強正則圖 (40){14,7;1,7}
26(4,6)-籠{4,3,3;1,1,4}
27廣義四邊形 (2,4){10,8;1,5}
27廣義四邊形 (2,4) 減去 spread 1{8,6,1,;1,3,8}
27廣義四邊形 (2,4) 減去 spread 2{8,6,1,;1,3,8}
27Schläfli 圖{16,5;1,8}
28Chang 圖{12,5;1,4}
28(8,2)-Kneser 圖{15,8;1,10}
28區域性 13-Paley 圖{13,6,1;1,6,13}
30(15,7,3)-關聯圖{7,6,4;1,3,7}
32(8,1)-Hadamard 圖{8,7,4,1;1,4,7,8}
32Kummer 圖{6,5,4;1,2,6}
32Wells 圖{5,4,1,1;1,1,4,5}
35格拉斯曼圖 J_2(4,2){18,8;1,9}
354-奇圖{4,3,3;1,1,2}
36六元碼圖{6,5,4,1;1,2,5,6}
36(9,2)-Kneser 圖{21,10;1,15}
36Sylvester 圖{5,4,2;1,1,4}
38(19,9,4)-關聯圖{9,8,5;1,4,9}
42(21,16,12)-關聯圖{16,15,4;1,12,16}
42(5,6)-籠{5,4,4;1,1,5}
42Hoffman-Singleton 圖 減去星{6,5,1;1,1,6}
45(10,2)-Kneser 圖{28,12;1,21}
45廣義八邊形 (2,1){4,2,2,2;1,1,1,2}
45半 Foster 圖{6,4,2,1;1,1,4,6}
46(23,11,5)-關聯圖{11,10,6;1,5,11}
48(12,1)-Hadamard 圖{12,11,6,1;1,6,11;12}
50Hoffman-Singleton 圖{7,6;1,1}
50Hoffman-Singleton 圖補圖{42,6;1,36}
52廣義六邊形 (3,1){6,3,3;1,1,2}
55(11,2)-Kneser 圖{36,14;1,28}
56Gosset 圖 的距離 2-圖{27,16,1;1,16,27}
56Gewirtz 圖{10,9;1,2}
56Gosset 圖{27,10,1;1,10,27}
57Perkel 圖{6,5,2;1,1,3}
62(31,15,7)-關聯圖{15,14,8;1,7,15}
62(31,25,20)-關聯圖{25,24,5;1,20,25}
62(6,6)-籠{6,5,5;1,1,6}
63(63,32,16,16)-強正則圖{32,15;1,16}
63完全圖 K_9 的辛 7-覆蓋{8,6,1;1,1,8}
64(1,1)-Doob 圖{9,6,3;1,2,3}
6464-分圓圖{21,12;1,6}
65Hall 圖{10,6,4;1,2,5}
66(12,2)-Kneser 圖{45,16;1,36}
70(35,17,8)-關聯圖{17,16,9;1,8,17}
70(7,3)-二部 Kneser 圖{4,3,3,2,2,1,1;1,1,2,2,3,3,4}
70(8,4)-Johnson 圖{16,9,4,1;1,4,9,16}
72Suetake 圖{12,11,8,1;1,4,11,12}
74(37,9,2)-關聯圖{9,8,7;1,2,9}
77M22 圖{16,15;1,4}
78(13,2)-Kneser 圖{55,18;1,45}
80(40,13,4)-關聯圖{13,12,9;1,4,13}
80(4,8)-籠{4,3,3,3;1,1,1,4}
81Brouwer-Haemers 圖{20,18;1,6}
91(14,2)-Kneser 圖{66,20;1,55}
94(47,23,11)-關聯圖{23,22,12;1,11,23}
100Hoffman-Singleton 圖的二部雙覆蓋{7,6,6,1,1;1,1,6,6,7}
100Hoffman-Singleton 圖 中的團{15,14,10,3;1,5,12,15}
100Hall-Janko 圖{36,21;1,12}
100Higman-Sims 圖{22,21;1,6}
105廣義六邊形 (4,1){8,4,4;1,1,2}
112Gewirtz 圖的二部雙覆蓋{10,9,8,2,1;1,2,8,9,10}
112廣義四邊形 (3,9){30,27;1,10}
114(57,49,42)-關聯圖{49,48,7;1,42,49}
114(8,6)-籠{8,7,7;1,1,8}
120(120,56,28,24)-強正則圖{56,27;1,24}
120(120,63,30,36)-強正則圖{63,32;1,36}
1265-奇圖{5,4,4,3;1,1,2,2}
126(9,4)-Johnson 圖{20,12,6,2;1,4,9,16}
126Zara 圖{45,32;1,18}
130格拉斯曼圖 J_3(4,2){48,27;1,16}
144半 Leonard 圖 (2){66,35;1,30}
146(73,64,56)-關聯圖{64,63,8;1,56,64}
146(9,6)-籠{9,8,8;1,1,9}
154M22 圖的二部雙覆蓋{16,15,12,4,1;1,4,12,15,16}
155格拉斯曼圖 J_2(5,2){42,24;1,9}
160廣義八邊形 (2,1){6,3,3,3;1,1,1,2}
162McLaughlin 圖 的第二個子構成圖{105,32;1,60}
162區域性 McLaughlin 圖{56,45;1,24}
162van Lint-Schrijver 圖{6,5,5,4;1,1,2,6}
170(5,8)-籠{5,4,4,4;1,1,1,5}
170(5,8)-籠{5,4,4,4;1,1,1,5}
175Hoffman-Singleton 圖的線圖{12,6,5;1,1,4}
176(176,70,18,34)-強正則圖{70,51;1,34}
176(176,105,68,54)-強正則圖{105,35;1,54}
182(10,6)-籠{10,9,9;1,1,10}
186廣義六邊形 (5,1){10,5,5;1,1,2}
189廣義十二邊形 (2,1){4,2,2,2,2,2;1,1,1,1,1,2}
200Higman-Sims 圖的二部雙覆蓋{22,21,16,6,1;1,6,16,21,22}
210(10,4)-Johnson 圖{24,15,8,3;1,4,9,16}
243Berlekamp-van Lint-Seidel 圖{22,20;1,2}
253(253,112,36,60)-強正則圖{112,75;1,60}
256(1,2)-Doob 圖{15,12,9,6,3;1,2,3,4,5}
266Livingstone 圖{11,10,6,1;1,1,5,11}
275McLaughlin 圖{112,81;1,56}
288Leonard 圖{12,11,8,1;1,4,11,12}
312(6,8)-籠{6,5,5,5;1,1,1,6}
315Hall-Janko 近八邊形{10,8,8,2;1,1,4,5}
416G_2(4) 圖{100,63;1,20}
425廣義八邊形 (4,1){8,4,4,4;1,1,1,2}
4626-奇圖{6,5,5,4,4;1,1,2,2,3}
506截斷 Witt 圖{15,14,12;1,1,9}
651格拉斯曼圖 J_2(6,2){90,56;1,9}
759大 Witt 圖{30,28,24;1,3,15}
1024(1,3)-Doob 圖{15,12,9,6,3;1,2,3,4,5}
1024(2,1)-Doob 圖{15,12,9,6,3;1,2,3,4,5}
1170(9,8)-籠{9,8,8,8;1,1,1,9}
1395格拉斯曼圖 J_2(6,3){98,72,32;1,9,49}

另請參閱

自同構圖, Biggs-Smith 圖, Coxeter 圖, 三次對稱圖, 立方圖, Desargues 圖, 距離傳遞圖, 十二面體圖, Foster 圖, 全域性引數, Heawood 圖, 相交陣列, Moore 圖, Pappus 圖, Petersen 圖, 正則圖, Shrikhande 圖, Sylvester 圖, Taylor 圖, Wells 圖

使用 探索

參考文獻

Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; and Faradžev, I. A. "Example of Graph without a Transitive Automorphism Group." Dokl. Akad. Nauk SSSR 185, 975-976, 1969. English version Soviet Math. Dokl. 10, 440-441, 1969.Bendito, E.; Carmona, A.; and Encinas, A. M. "Shortest Paths in Distance-Regular Graphs." Europ. J. Combin. 21, 153-166, 2000.Biggs, N.; Boshier, A.; and Shawe-Taylor, J. "Cubic Distance-Regular Graphs." J. London Math. Soc. S2-33, 385-394, 1986.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 13 and 159, 1993.Brouwer, A. "The Cubic Distance-Regular Graphs." http://www.win.tue.nl/~aeb/graphs/cubic_drg.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Brouwer, A. and Koolen, J. "The Distance-Regular Graphs of Valency Four." J. Algebraic Combin. 10, 5-24, 1999.Eppstein, D. "Cubic Symmetric xyz Graphs." Oct. 16, 2007. http://11011110.livejournal.com/120326.html.Fiol, M. A. and Garriga, E. "From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs." J. Combin. Th. B 71, 162-183, 1997.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 68-69, 2001.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Haemers, W. H. "Distance-Regularity and the Spectrum of Graphs." Linear Alg. Appl. 236, 265-278, 1996.Koolen, J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular Graphs of Diameter at Least 3 With Smallest Eigenvalue at Least -3." 15 Nov 2023. https://arxiv.org/abs/2311.09001.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs" http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." 19 Feb 2024. https://arxiv.org/abs/2402.11758.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

在 中被引用

距離正則圖

請這樣引用

Weisstein, Eric W. "距離正則圖。" 來自 Web 資源。 https://mathworld.tw/Distance-RegularGraph.html

主題分類