主題
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.tw/Distance-TransitiveGraph.html

主題分類