主题
Search

距离传递图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

如果图 G 的 自同构群 在图中每个成对距离的顶点对上是 传递的，则该图是距离传递的。距离传递性是 距离正则性 的推广。

每个距离传递图都是 距离正则的，但反之不一定成立，正如 Adel'son-Vel'skii等人首次证明的那样（1969；Brouwer等人1989，第 136 页）。最小的非距离传递的 距离正则图 是 Shrikhande 图（Brouwer等人1989，第 136 页）。

虽然最常见的是仅考虑连通的距离传递图，但上述定义同样适用于非连通图，其中除了整数图距离外，不同连通分量中的顶点对被认为距离为无穷大。

对于每个给定的顶点度 >2，存在有限多个距离传递图（Brouwer等人1989，第 214 页和 220 页）。此外，所有 顶点度 <=13 的距离传递图都是已知的（Brouwer等人1989，第 221-225 页），如下表所示。

顶点数为 n=1、2、... 的距离传递图的数量为 1、2、2、4、3、7、3、9、6、11、... (OEIS A308601)，这与 n=9 以内的 对称图 的数量一致。最小的 对称 但非距离传递的图是 循环图 Ci_10(1,4)。

几种常见的图族是距离传递的，但实际上，具有此属性的图非常罕见（Biggs 1993，第 158 页）。

距离传递图族包括

1. 二分 Kneser 图 H(2n-1,n-1) (即 奇图 O_n 的 二分双图)，

2. 鸡尾酒会图 K_(n×2) ，

3. 完全二分图 K_(n,n),

4. 完全图 K_n,

5. 完全 k-部图 K_(m×n),

6. 冠图 K_2 square K_n^_,

7. 空图 K^__n,

8. 折叠立方体图 square _n,

9. 格拉斯曼图 J_q(n,k),

10. 半立方体图 Q_n/2,

11. 超立方体图 Q_n,

12. 约翰逊图 J(n,k),

13. 梯子阶梯图 nP_2,

14. 奇图 (Brouwer等人1989，第 222 页，定理 7.5.2)，

15. 佩利图，

16. 车图 K_n square K_n,

17. 车补图 K_n square K_n^_,

18. 四面体约翰逊图 J(n,3)，和

19. 三角形图 L(K_n)。

Distance-TransitiveGraph3

阶数为 3 的连通距离传递图总结在下表中。

n图相交数组
4四面体图 K_4{3;1}
6效用图 K_(3,3){3,2;1,3}
8立方体图 Q_3{3,2,1;1,2,3}
10彼得森图 P{3,2;1,1}
14希伍德图{3,2,2;1,1,3}
18帕普斯图{3,2,2,1;1,1,2,3}
20德扎格图{3,2,2,1,1;1,1,2,2,3}
20十二面体图{3,2,1,1,1;1,1,1,2,3}
28考克斯特图{3,2,2,1;1,1,1,2}
30图特 8-笼{3,2,2,2;1,1,1,3}
90福斯特图{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
102比格斯-史密斯图{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Distance-TransitiveGraph4

阶数为 4 的连通距离传递图总结在下表中（Brouwer等人1989，第 222 页）。

n图相交数组
6完全图 K_6{5;1}
10完全二分图 K_(5,5){5,4;1,5}
12冠图 K_2 square K_6^_{5,4,1;1,4,5}
12二十面体图{5,2,1;1,2,5}
16克莱布什图{5,4;1,2}
222-(11,5,2) 设计的 Levi 图{5,4,3;1,2,5}
325-超立方体图{5,4,3,2,1;1,2,3,4,5}
32韦尔斯图{5,4,1,1;1,1,4,5}
36西尔维斯特图{5,4,2;1,1,4}
42(5,6)-笼图{5,4,4;1,1,5}
= 广义六边形 GH(1,4)
50AG(2,5) 减去一个平行类{5,4,4,1;1,1,4,5}
126奇图 O_5{5,4,4,3;1,1,2,2}
170(5,8)-笼图{5,4,4,4;1,1,1,5}
= 广义八边形 GO(1,4)
252二分 Kneser 图 H(9,4){5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5}
= 奇图 O_5 的 二分双图
Distance-TransitiveGraph6

阶数为 6 的连通距离传递图总结在下表中（Brouwer等人1989，第 223 页）。

n图相交数组
7完全图 K_7{6;1}
816-胞 图 K_(4×2){6,1;1,6}
9完全三分图 K_(3,3,3){6,2;1,6}
10三角形图 L(K_5){6,2;1,4}
12完全二分图 K_(6,6){6,5;1,6}
1313-佩利图{6,3;1,3}
14冠图 K_2 square K_7^_{6,5,1;1,5,6}
15广义四边形 GQ(2,2){6,4;1,3}
16车图 K_4 square K_4{6,3;1,2}
22(11,6,3)-Levi 图{6,5,3;1,3,6}
27(3,3)-汉明图{6,4,2;1,2,3}
32库默尔图 square _6{6,5,4;1,2,6}
36六元码图{6,5,4,1;1,2,5,6}
= 来自 RT[6,2;3] 的 3·K_(6,6)
42霍夫曼-辛格尔顿图 减去星{6,5,1;1,1,6}
45半 福斯特图{6,4,2,1;1,1,4,6}
52广义六边形 GH(3,1){6,3,3;1,1,2}
57珀克尔图{6,5,2;1,1,3}
62(6,6)-笼图{6,5,5;1,1,6}
63广义六边形 GH(2,2) 及其对偶的第一点图{6,4,4;1,1,3}
63广义六边形 GH(2,2) 及其对偶的第二点图{6,4,4;1,1,3}
64超立方体图 Q_6{6,5,4,3,2,1;1,2,3,4,5,6}
462奇图 O_6{6,5,5,4,4;1,1,2,2,3}
924二分 Kneser 图 H(11,5){6,5,5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5,5,6}
= 奇图 O_6 的 二分双图
1456广义十二边形 GD(3,1){6,3,3,3,3,3;1,1,1,1,1,2}
Distance-TransitiveGraph7

阶数为 7 的连通距离传递图总结在下表中（Brouwer等人1989，第 223 页）。

n图相交数组
8完全图 K_8{7;1}
14完全二分图 K_(7,7){7,6;1,7}
16冠图 K_2 square K_8^_{7,6,1;1,6,7}
30(15,7,3)-Levi 图{7,6,4;1,3,7}
50霍夫曼-辛格尔顿图{7,6;1,1}
64折叠立方体图 square _7{7,6,5;1,2,3}
98AG(2,7) 减去一个平行类{7,6,6,1;1,1,6,7}
100霍夫曼-辛格尔顿图 的 二分双图{7,6,6,1,1;1,1,6,6,7}
128超立方体图 Q_7{7,6,5,4,3,2,1;1,2,3,4,5,6,7}
310格拉斯曼图 J_2(5,2) 的 二分双图{7,6,6,4,4;1,1,3,3,7}
330S(5,8,24) 的 2-残差{7,6,4,4;1,1,1,6}
= 双重截断维特图
990伊万诺夫-伊万诺夫-法拉杰夫图{7,6,4,4,4,1,1,1;1,1,1,2,4,4,6,7}
1716奇图 O_7{7,6,6,5,5,4;1,1,2,2,3,3}
3432二分 Kneser 图 H(13,6){7,6,6,5,5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5,5,6,6,7}
= 奇图 O_7 的 二分双图
Distance-TransitiveGraph8

阶数为 8 的连通距离传递图总结在下表中（Brouwer等人1989，第 223-224 页）。

n图相交数组
9完全图 K_9{8;1}
10鸡尾酒会图 K_(5×2){8,1;1,8}
12完全三分图 K_(4,4,4){8,3;1,8}
15三角形图 L(K_6){8,3;1,4}
16完全二分图 K_(8,8){8,7;1,8}
1717-佩利图{8,4;1,4}
18冠图 K_2 square K_9^_{8,7,1;1,7,8}
25车图 K_5 square K_5{8,4;1,2}
27广义四边形 GQ(2,4){8,6,1;1,3,8}
302-(15,8,4) 设计的 Levi 图{8,7,4;1,4,8}
32(8,1)-哈达玛图{8,7,4,1;1,4,7,8}
64= 来自 RT[8,2;4] 的 4·K_(8,8){8,7,6,1;1,2,7,8}
81(4,3)-汉明图{8,6,4,2;1,2,3,4}
105广义六边形 GH(4,1){8,4,4;1,1,2}
114(8,6)-笼图{8,7,7;1,1,8}
128折叠立方体图 square _8{8,7,6,5;1,2,3,8}
128AG(2,8) 减去一个平行类{8,7,7,1;1,1,7,8}
256超立方体图 Q_8{8,7,6,5,4,3,2,1;1,2,3,4,5,6,7,8}
425广义八边形 GO(4,1){8,4,4,4;1,1,1,2}
6435奇图 O_8{8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
12870二分 Kneser 图 H(15,7)
= 奇图 O_8 的 二分双图
Distance-TransitiveGraph9

阶数为 9 的连通距离传递图总结在下表中（Brouwer等人1989，第 224 页）。

n图相交数组
10完全图 K_(10){9;1}
12完全 4-部图 K_(4×3){9,2;1,9}
16车补图 K_4 square K_4^_{9,4;1,6}
18完全二分图 K_(9,9){9,8;1,9}
20冠图 K_2 square K_(10)^_{9,8,1;1,8,9}
20四面体约翰逊图 L(K_6){9,4,1;1,4,9}
26(13,9,6)-Levi 图{9,8,3;1,6,9}
= (13,9,6)-差集 Levi 图
54= 来自 RT[9,3;3] 的 3·K_(9,9){9,8,6,1;1,3,8,9}
= 对称横向设计的 Levi 图 STD_2[9,3]
64(3,4)-汉明图{9,6,3;1,2,3}
146(9,6)-笼{9,8,8;1,1,9}
162AG(2,9) 减去一个平行类{9,8,8,1;1,1,8,9}
256折叠立方体图 square _9{9,8,7,6;1,2,3,4}
280PG(2,4) 中的 unital{9,8,6,3;1,1,3,8}
1170(9,8)-笼{9,8,8,8;1,1,1,9}
24310奇图 O_9{8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
48620二分 Kneser 图 H(17,9)
= 奇图 O_9 的 二分双图
Distance-TransitiveGraph10

阶数为 10 的连通距离传递图总结在下表中（Brouwer等人1989，第 224 页）。

n图相交数组
11完全图 K_(11){10;1}
12鸡尾酒会图 K_(6×2){10,1;1,10}
15完全三分图 K_(5,5,5){10,4;1,10}
16半立方体图 Q_5/2{10,3;1,6}
20完全二分图 K_(10,10){10,9;1,10}
21克内泽尔图 K(7,2){10,6;1,6}
21三角形图 L(K_7){10,4;1,4}
22冠图 K_2 square K_(11)^_{10,9,1;1,9,10}
27广义四边形 GQ(2,4){10,8;1,5}
322-(16,10,6) 设计的第一个 Levi 图{10,9,4;1,6,10}
= 折叠立方体图 square _6 的 距离-3 图
36车图 K_6 square K_6{10,5;1,2}
56格维尔茨图{10,9;1,2}
63康威-史密斯图{10,6,4,1;1,2,6,10}
65霍尔图{10,6,4;1,2,5}
112格维尔茨图 的 二分双图{10,9,8,2,1;1,2,8,9,10}
182(10,6)-笼图{10,9,9;1,1,10}
186广义六边形 GH(5,1){10,5,5;1,1,2}
243(5,3)-汉明图{10,8,6,4,2;1,2,3,4,5}
315霍尔-扬科近八边形{10,8,8,2;1,1,4,5}
512折叠立方体图 square _(10){10,9,8,7,6;1,2,3,4,10}
1755广义八边形 GO(2,4){10,8,8,8;1,1,1,5}
92378奇图 O_(10){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
132860广义十二边形 GD(1,9){10,9,9,9,9,9;1,1,1,1,1,10}
184756二分 Kneser 图 H(19,10)
= 奇图 O_(10) 的 二分双图
Distance-TransitiveGraph11

阶数为 11 的连通距离传递图总结在下表中（Brouwer等人1989，第 224 页）。

n图相交数组
12完全图 K_(12){11;1}
22完全二分图 K_(11,11){11,10;1,11}
24冠图 K_2 square K_(12)^_{11,10,1;1,10,11}
242AG(2,11) 减去一个平行类{11,10,10,1;1,1,10,11}
266利文斯顿图{11,10,6,1;1,1,5,11}
352716奇图 O_(11){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
705432二分 Kneser 图 H(21,11)
= 奇图 O_(11) 的 二分双图
Distance-TransitiveGraph12

阶数为 12 的连通距离传递图总结在下表中（Brouwer等人1989，第 224-225 页）。

n图相交数组
13完全图 K_(13){12;1}
14鸡尾酒会图 K_(7×2){12,1;1,12}
15完全 5-部图 K_(5×3){12,2;1,12}
16完全 4-部图 K_(4×4){12,3;1,12}
18完全三分图 K_(6,6,6){12,5;1,12}
24完全二分图 K_(12,12){12,11;1,12}
2525-佩利图{12,6;1,6}
26冠图 K_2 square K_(13)^_{12,11,1;1,11,12}
28三角形图 L(K_8){12,5;1,4}
35四面体约翰逊图 J(3,7){12,6,2;1,4,9}
40广义四边形 GQ(3,3) 及其对偶的第一点图{12,9;1,4}
40广义四边形 GQ(3,3) 及其对偶的第二点图{12,9;1,4}
45广义四边形 GQ(4,2) 的点图{12,8;1,3}
48(12,1)-哈达玛图{12,11,6,1;1,6,11,12}
49车图 K_7 square K_7{12,6;1,2}
68多罗图{12,10,3;1,3,8}
= PSigmaL(2,16)
125(3,5)-汉明图{12,8,4;1,2,3}
175霍夫曼-辛格尔顿图 的 线图{12,6,5;1,1,4}
208PGammaU(3,4) 在非各向同性点上{12,10,5;1,1,8}
256(4,4)-汉明图{12,9,6,3;1,2,3,4}
266广义六边形 GH(1,11){12,11,11;1,1,12}
364广义六边形 GH(3,3) 及其对偶的点图{12,9,9;1,1,4}
729(6,3)-汉明图{12,10,8,6,4,2;1,2,3,4,5,6}
2925广义八边形 GO(4,2){12,8,8,8;1,1,1,3}
1352078奇图 O_(12){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
2704156二分 Kneser 图 H(23,11)
= 奇图 O_(12) 的 二分双图
Distance-TransitiveGraph13

阶数为 13 的连通距离传递图总结在下表中（Brouwer等人1989，第 225 页）。

n图相交数组
14完全图 K_(14){13;1}
26完全二分图 K_(13,13){13,12;1,13}
28冠图 K_2 square K_(14)^_{13,12,1;1,12,13}
2828-泰勒图{13,6,1;1,6,13}
80(40,13,4)-Levi 图{13,12,9;1,4,13}
338AG(2,13) 减去一个平行类{13,12,12,1;1,1,12,13}
2420格拉斯曼图 J_3(5,2) 的加倍{13,12,12,9,9;1,1,4,4,13}
5200300奇图 O_(13){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
10400600二分 Kneser 图 H(25,12)
= 奇图 O_(13) 的 二分双图

参见

二分双图、康威-史密斯图、距离正则图、全局参数、半图、超立方体图、相交数组、利文斯顿图、局部图、奇图、Shrikhande 图、铃木图

使用 探索

参考文献

Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; 和 Faradžev, I. A. "没有传递自同构群的图的例子。" Dokl. Akad. Nauk SSSR 185, 975-976, 1969. 英文版 Soviet Math. Dokl. 10, 440-441, 1969.Biggs, N. L. "距离传递图。" 第 20 章，见 代数图论，第二版 剑桥，英格兰：剑桥大学出版社，页 155-163, 1993.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. "距离传递图。" 第 7 章，见 距离正则图。 纽约：施普林格出版社，页 214-234, 1989.DistanceRegular.org. http://www.distanceregular.org.Godsil, C. 和 Royle, G. "距离传递图。" §4.5，见 代数图论。 纽约：施普林格出版社，页 66-69, 2001.Sloane, N. J. A. 序列 A308601

在 上被引用

距离传递图

以此引用

Weisstein, Eric W. "距离传递图。" 来自 —— 资源。 https://mathworld.net.cn/Distance-TransitiveGraph.html

主题分类