对称图

对称图是一个图，它既是边传递的又是顶点传递的（Holton 和 Sheehan 1993, p. 209）。

然而，必须谨慎对待这个定义，因为弧传递图或 1-弧传递图有时也被称为对称图（Godsil 和 Royle 2001, p. 59）。当存在一些图，它们在顶点传递和边传递的意义上是对称的，但不是弧传递的，这可能会特别令人困惑。换句话说，存在这样的图，其中任何边都可以映射到任何其他边——但只有两种可能的方式中的一种。Tutte (1966) 首先考虑了这类图，他表明任何这样的图都必须是偶数度的正则图。Bouwer (1970) 给出了第一个例子，他最小的例子有 54 个顶点，是四次图。Dolye (1976) 和 Holt (1981) 随后和独立地发现了一个美丽的 27 个顶点的四次对称图，称为Doyle 图（或有时称为 Holt 图），它不是弧传递的。这个图可以从 Bouwer 的 54 顶点图通过识别直径相对的顶点对获得（Doyle 1998）。

一个正则图，它是边传递的但不是顶点传递的，被称为半对称图。

对称图的图补和线图都不一定是对称的。

对称图总是正则图。节点数为 , 2, ... 的对称图的数量分别为 1, 2, 2, 4, 3, 7, 3, 9, ...，上面说明了其中的一些。这些是完全图 ; 圈图 , ; , ; , 循环图 , , 八面体图, 以及。

下表给出了其他命名的对称图的列表。

图	顶点数
四面体图	4
完全图	5
八面体图 (循环图 )	6
(效用图)	6
完全图	6
16-胞体	8
立方体图	8
Petersen 图	10
立方八面体图	12
二十面体图	12
Heawood 图	14
Clebsch 图	16
Moebius-Kantor 图	16
四维超立方体	16
Pappus 图	18
十二面体图	20
Desargues 图	20
Doyle 图	27
Coxeter 图	28
Tutte 8-笼	30
icosidodecahedral 图	30
Dyck 图	32
Foster 图	90
Biggs-Smith 图	102

参见

弧传递图, 自同构群, Bouwer 图, 三次对称图, Doyle 图, 边传递图, 图自同构, 单位图, 四次对称图, 顶点传递图

在上探索

更多尝试

参考文献

Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.Chao, C.-Y. "On the Classification of Symmetric Graphs with a Prime Number of Vertices." Trans. Amer. Math. Soc. 158, 247-256, 1971.Cheng, Y. and Oxley, J. "On Weakly Symmetric Graphs of Order Twice a Prime." J. Combin. Th. Ser. B 42, 196-211, 1987.Doyle, P. G. On Transitive Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. http://hilbert.dartmouth.edu/~doyle/docs/bouwer/bouwer/bouwer.html.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. "Symmetric Graphs" and "Highly Symmetric Graphs." Graph Theory. Reading, MA: Addison-Wesley, pp. 171-175, 1994.Holt, D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J. Graph Th. 5, 201-204, 1981.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Praeger, C.; Wang, R. J.; and Xu, M. Y. "Symmetric Graphs of Order a Product of Two Distinct Primes." J. Combin. Th. Ser. B 58, 299-318, 1993.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A087145 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. Connectivity in Graphs. Toronto, CA: University of Toronto Press, 1966.Wang, R. J. and Xu, M. Y. "A Classification of Symmetric Graphs of Order