弧傳遞圖

弧傳遞圖，有時也稱為旗傳遞圖，是一種圖，其圖自同構群在其圖弧上傳遞地作用（Godsil 和 Royle 2001, p. 59）。

更一般地，一個圖 被稱為 -弧傳遞（或簡稱為“-傳遞”）的，其中 ，如果它有一個 s-路徑，並且總是存在一個 圖自同構，將 的每個 s-路徑 對映到任何其他的 -s-路徑 (Harary 1994, p. 173)。換句話說，一個圖是 -傳遞的，如果它的 自同構群 在所有 s-路徑 上傳遞地作用（Holton 和 Sheehan 1993, p. 203）。請注意，不同的作者更喜歡使用 以外的符號，例如 (Harary 1994, p. 173) 或 。

弧傳遞性是比 邊傳遞性 或 頂點傳遞性 更強的性質，因此弧傳遞圖具有非常高的對稱性。

0-傳遞圖是 頂點傳遞 的。1-傳遞圖簡稱為“弧傳遞圖”甚至“傳遞圖”。更令人困惑的是，弧傳遞圖（因此實際上是 -傳遞圖，對於 ）有時被稱為 對稱圖 (Godsil 和 Royle 2001, p. 59)。這種術語衝突特別令人困惑，因為正如 Bouwer (1970) 首次表明的那樣，存在 對稱（在邊和頂點傳遞的意義上）但不是弧傳遞的圖，最小的已知例子是 Doyle 圖。

對稱 的非弧傳遞圖首先由 Tutte (1966) 考慮，他表明任何這樣的圖都必須是 正則 的偶數度。第一個例子由 Bouwer (1970) 給出，他為所有整數 給出了一個連通的 -正則對稱弧非傳遞圖的構造性證明。最小的 Bouwer 圖 有 54 個頂點，是 四次圖。 對稱 的非弧傳遞圖的另一個例子是 G. Exoo (E. Weisstein, 7 月 16 日, 2018) 發現的 111 個頂點上的 6-正則非平面直徑為 3 的圖。

一個連通圖 ，沒有 端點（即，最小頂點度 ），被稱為嚴格 -傳遞的（其中 ），如果 是 -傳遞的，但不是 -傳遞的 (Holton 和 Sheehan 1993, p. 206)。這樣的圖也被稱為 -正則 (Tutte 1947, Coxeter 1950, Frucht 1952) 和 -單傳遞 (Harary 1994, p. 174)。一個嚴格 -傳遞圖 對於任意兩個 -路徑 和 ，恰好有一個自同構 使得 (Harary 1994, p. 174)。

圈圖 （對於 ）對於所有 都是 -傳遞的， 對於任何正整數 也是如此 (Holton 和 Sheehan 1993, p. 204)。

頂點數為 , 2, ... 的弧傳遞圖的數量為 0, 1, 1, 3, 2, 6, 2, 8, 5, ... (OEIS A180240)，如下表總結，其中 表示 路徑圖, 表示 圈圖, 是 梯子梯級圖, 是 完全圖, 是 完全二部圖, 是 完全三部圖, 是 超立方體圖, 是 迴圈圖, 並且 是 份 的 圖並。

2
3
4	, ,
5	,
6	, , , 八面體圖 , , 效用圖
7	,
8	, , , 立方圖 , , , 16-胞體圖 ,
9	, , , 廣義四邊形 ,

頂點數為 , 2, ... 的連通弧傳遞圖的數量為 0, 1, 1, 2, 2, 4, 2, 5, 4, 8, ... (OEIS A286280)。

樹 可能是 -傳遞的，但不是 -傳遞的。例如，星圖 ，其中 是邊傳遞和 2-傳遞的，但不是 1-傳遞的。然而，不是樹的 -傳遞圖也是 -傳遞的，對於所有 (Holton 和 Sheehan 1993, p. 204)，因此最清楚地稱為“嚴格 -傳遞”。

路徑圖 是 -傳遞的 (Holton 和 Sheehan 1993, p. 203)，並且 圈圖 () 是 -傳遞的 (Holton 和 Sheehan 1993, pp. 204 和 209, 練習 6)。

如果 是一個 -傳遞圖，那麼 對於任何 也是 -傳遞的 (Holton 和 Sheehan 1993, p. 204)。但是如果 是不連通的，並且不是 份單一型別圖的並集，那麼它不是 頂點傳遞 的，因此也不是弧傳遞的。因此，不連通圖要麼與其相同的連通分量具有相同的 -傳遞性，要麼不是弧傳遞的（如果它們的分量不相同）。因此，不連通圖的 -傳遞性是微不足道的。

1947 年，Tutte 表明，對於任何嚴格 -傳遞的連通 三次圖， (Holton 和 Sheehan 1993, p. 207; Harary 1994, p. 175; Godsil 和 Royle 2001, p. 63)。Weiss (1974) 隨後建立了非常 深刻的 結果，即對於度為 的任何正則連通嚴格 -傳遞圖， 或 (Holton 和 Sheehan 1993, p. 208; Godsil 和 Royle 2001, p. 63)。

如果 是一個 頂點傳遞 的 三次圖，在 個頂點上，並且 是它的 自同構群，那麼如果 3 整除 頂點 的穩定子 的階，則 是弧傳遞的 (Godsil 和 Royle 2001, p. 75)。

由於對於 ，不存在 -傳遞的 三次圖，因此也不存在嚴格 -傳遞的三次圖 (Harary 1994, p. 175)。3-籠是嚴格 -傳遞的，對於 (Harary 1994, p. 175)，但也存在嚴格 -傳遞的圖，對於 ，它們不是 籠圖 (Harary 1994, p. 175)。這些包括 Frucht (1952) 發現的周長為 12 的 432 個節點上的嚴格 1-傳遞圖，構造為排列 (2, 1, 5, 8, 3, 6, 7, 4, 9), (3, 6, 1, 4, 9, 2, 7, 8, 5) 和 (4, 3, 2, 1, 5, 7, 6, 8, 9) 的 Cayley 圖，現在更普遍地稱為 三次對稱圖 ；嚴格 2-傳遞的 立方圖，十二面體圖，Möbius-Kantor 圖 ，和 Nauru 圖；以及嚴格 3-傳遞的 Desargues 圖 (Coxeter 1950)。上面說明並總結在下表中的一些嚴格 -傳遞圖（部分基於 Coxeter 1950 和 Harary 1994, p. 175 給出的表格）。

			圖
1	432	3	三次對稱圖
2	4	3	四面體圖
2	8	3	立方圖
2	16	3	Möbius-Kantor 圖
2	16	4	四維超立方體圖
2	20	3	十二面體圖
2	24	3	Nauru 圖
2	32	5	5-超立方體圖
2	32	6	Kummer 圖
2	64	6	6-超立方體圖
2	128	7	7-超立方體圖
2	256	8	8-超立方體圖
3	6	3	效用圖
3	20	3	Desargues 圖
4	14	3	Heawood 圖
5	30	3	Tutte 8-籠