弧传递图

弧传递图，有时也称为旗传递图，是一种图，其图自同构群在其图弧上传递地作用（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-笼