主题
Search

半对称图


一个正则图,它是边传递的但不是顶点传递的,被称为半对称图 (Marušič and Potočnik 2001)。相反,任何既是边传递又是顶点传递的图都被称为对称图

注意,一个图可能是边传递的,但既不是顶点传递的也不是正则的。一个例子是Pasch 图,因此它不是半对称图。其他例子包括星图菱形十二面体图菱形三十面体图Schläfli 双六图

每个半对称图必然是二部图,其两部分大小相等,且自同构群在这两部分上传递作用。在 n=1, 2, ... 个节点上的正则二部图的数量是 1, 2, 1, 3, 1, 4, 1, 6, 1, ... (OEIS A087114)。

Folkman (1967) 证明了不存在阶数为 2p 的半对称图,其中 p 是一个素数,并构造了一些阶数为 2pq 的半对称图,其中 pq 是素数且 p=1 (mod q),包括所谓的 Folkman 图。Folkman (1967) 还询问是否存在阶数为 30 的半对称图,Ivanov (1987) 随后给出了否定回答。

SemisymmetricGraphs

不存在少于 20 个顶点的半对称图 (Skiena 1990, p. 186)。上面展示了半对称图的例子,并在下表中进行了总结。


另请参阅

立方半对称图, 边传递图, Folkman 图, Gray 图, Iofinova-Ivanov 图, Ivanov-Ivanov-Faradjev 图, Ljubljana 图, 对称图, 顶点传递图

使用 Wolfram|Alpha 探索

参考文献

Bouwer, I. A. "关于边传递但非顶点传递的正则图。" J. Combin. Th. Ser. B 12, 32-40, 1972.Du, S.-F. 和 Marus_ic_, D. "无限的双本原半对称图族。" J. Graph Th. 32, 217-228, 1999.Du, S. 和 Xu, M. "阶数为 2pq 的半对称图的分类。" Comm. Alg. 28, 2685-2715, 2000.Folkman, J. "正则线对称图。" J. Combin. Th. 3, 215-232, 1967.Ivanov, A. V. "关于边传递但非顶点传递的正则图。" 在 组合设计理论 (Ed. C. J. Colbourn and R. Mathon)。荷兰阿姆斯特丹:North-Holland, pp. 273-285, 1987.Iofinova, M. E. and Ivanov, A. A. "双本原立方图。" 在 组合对象的代数理论研究。 pp. 123-134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137-152, 1985.)Klin, M. H. "关于边传递但非顶点传递的图。" 在 图论中的代数方法,第一卷,第二卷:1978 年 8 月 24-31 日在塞格德举行的会议论文集 (Ed. L. Lovász and V. T. Sós)。荷兰阿姆斯特丹:North-Holland, pp. 399-403, 1981.Lipschutz, S. and Xu, M.-Y. "关于三价半对称图的无限族的注释。" European J. Combin. 23, 707-711, 2002.Marušič, D. and Potočnik, P. "广义 Folkman 图的半对称性。" European J. Combin. 22, 333-349, 2001.Marušič, D.; Pisanski, T.; and Wilson, S. "GRAY [原文如此] 图的亏格为 7。" Europ. J. Combin. 26, 377-385, 2005.Skiena, S. 离散数学实现:使用 Mathematica 的组合数学和图论。 美国马萨诸塞州雷丁:Addison-Wesley, 1990.Sloane, N. J. A. 整数序列在线百科全书中的序列 A087114

在 Wolfram|Alpha 中引用

半对称图

请引用为

Weisstein, Eric W. "半对称图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/SemisymmetricGraph.html

主题分类