主题
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 图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

距离正则图

请这样引用

Weisstein, Eric W. "距离正则图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Distance-RegularGraph.html

主题分类