主题
Search

三次对称图

下载 Mathematica 笔记本下载 Wolfram 笔记本

三次对称图是一种对称三次图（即，度为 3 的正则图）。这类图最早由福斯特（Foster，1932）研究。此后，它们一直是人们关注和研究的对象。由于三次图必须具有偶数个顶点，因此三次对称图也必须如此。

鲍尔等人(1988) 发表了所有顶点数不超过 512 的连通三次对称图的数据。康德尔和多布萨尼（Conder and Dobcsányi，2002）找到了所有顶点数不超过 768 的三次对称图。罗伊尔维护了一个已知顶点数少于 1000 的三次对称图列表。（已知该列表对于最多 768 个顶点是完整的，但对于 770-998 个顶点仅包含凯莱图。）所有顶点数最多为 2048 的三次对称图随后由 M. Condor 在 2006 年 8 月枚举（Condor）。

CubicSymmetricDisconnectedGraphs

节点数为n=2, 4, 6, 8, ... 的不连通三次对称图的数量分别是 0, 0, 0, 1, ...，其中最小的一些如上所示。

CubicSymmetricGraphs

节点数不超过 102 的连通三次对称图如上图所示，表示为F_nZ，其中 F 代表福斯特（Foster），n 是顶点的数量，字母 A, B, C 等附加表示在 n 个顶点上的第一个、第二个等此类图（罗伊尔）。

许多连通三次对称图，包括F_(024)A，F_(060)A和F_(064)A都是凯莱图。F_(024)A与广义彼得森图GP(12,5)同构，并且由福斯特（1932）、考克斯特（Coxeter，1950）和弗鲁赫特（Frucht，1952）构造。弗鲁赫特（1952）讨论的“具有 64 个顶点和周长 8 的明显新的对称图”是F_(064)A。F_(120)B是正二十面体的滚动多面体图。

节点数为n=2, 4, ...的连通三次对称图的数量分别是 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, ... （OEIS A059282）。所有节点数不超过 60 的三次对称图都是哈密顿图，除了彼得森图（10 个节点）和考克斯特图（28 个节点），因此哈密顿连通三次对称图的数量分别是 0, 1, 1, 1, 0, 0, 1, 1, 1, 2, 0, 1, 1, ... (OEIS A091430)。连通三次对称图的前几个阶数是 4, 6, 8, 10, 14, 16, 18, 20, 20, 24, 26, 28, 30, 32, 38, 40, ... (OEIS A075124)。

下表总结了节点数不超过 102 的连通三次对称图。在此表中，H 表示哈密顿图，* 表示没有阶数>1的LCF 表示法的图。

F图哈密顿性LCF 表示法
4A四面体图是[-2]^4
6AK_(3,3) （效用图）是[3,-3]^3
8A立方体图是[3,-3]^4
10A彼得森图否--
14A希伍德图是[5,-5]^7
16A莫比乌斯-康托尔图是[5,-5]^8
18A帕普斯图是[5,7,-7,7,-7,-5]^3
20A十二面体图是[10,7,4,-4,-7,10,-4,7,-7,4]^2
20B德萨格图是[5,-5,9,-9]^5
24A瑙鲁图是[5,-9,7,-7,9,-5]^4
26AF_(26)A是[7,-7]^(13)
28A考克斯特图否--
30A塔特 8-笼是[-13,-9,7,-7,9,13]^5
32A戴克图是[5,-5,13,-13]^8
38AF_(38)A是[15,-15]^(19)
40AF_(40)A是[15,9,-9,-15]^(10)
42AF_(42)A是[9,-9]^(21)
48AF_(48)A是[-7,9,19,-19,-9,7]^8
50AF_(50)A是[-21,-19,19,-19,19,-19,19,21,-21,21]^5
54AF_(54)A是[-13,-11,11,-11,11,13]^9
56AF_(56)A是[13,-11,11,13]^(14)
56BF_(56)B是[-28,-19,-12,-18,12,15,-15,-12,18,12,19,-28,-18,18]^4
56CF_(56)C是*
60AF_(60)A是[12,-17,-12,25,17,-26,-9,9,-25,26]^6
62AF_(62)A是[11,-11]^(31)
64AF_(64)A是[23,-11,-29,25,-25,29,11,-23]^8
72AF_(72)A是[-31,9,-5,5,-9,31]^(12)
74AF_(74)A是[-21,21]^(37)
78AF_(78)A是[-33,33]^(39)
80AF_(80)A是[-25,9,-9,25]^(20)
84AF_(84)A是*
86AF_(86)A是[-13,13]^(43)
90A福斯特图是[17,-9,37,-37,9,-17]^(15)
96AF_(96)A是[-41,-39,39,41,-41,41,-41,41]^(12)
96BF_(96)B是[-45,-33,-15,45,-39,-21,-45,39,21,45,-15,15,-45,39,-39,45,33,27,-45,15,-27,45,-39,39]^4
98AF_(98)A是[-37,37]^(49)
98BF_(98)A是[-43,-41,41,-41,41,-41,41,-41,41,-41,41,43,-43,43]^7
102A比格斯-史密斯图是*
SymmetricCubicGraphsAlternateEmbeddings

上面的图显示了一些选定的三次对称图的替代嵌入。

UnitDistanceCubicSymmetric

许多三次对称图（除了四面体图、效用图以及其他可能的情况）都具有单位距离嵌入，如上面主要由 Gerbracht（2008 年，私人通信，2009 年 12 月至 2010 年 1 月）的嵌入所示。

另见

笼图，三次图，三次顶点传递图，距离正则图，LCF 表示法，四次对称图，五次对称图，对称图

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L. 代数图论，第二版 英国剑桥：剑桥大学出版社，第147 页，1993 年。Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; and Star, Z. 福斯特普查。 Charles Babbage 研究中心，1988 年。Conder, M. 和 Dobcsányi, P. “顶点数不超过 768 的三价对称图。”组合数学，组合计算杂志 40, 41-63, 2002。Conder, M. 和 Lorimer, P. “价数为 3 的对称图的自同构群。”组合理论杂志，B 系列 47, 60-72, 1989。Conder, M. 和 Nedela, R. “小周长的对称三次图。”组合理论杂志，B 系列 97, 757-768, 2007。Conder, M. “顶点数不超过 2048 的三价（三次）对称图。”http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt。Coxeter, H. S. M. “自对偶配置和正则图。”美国数学学会公报 56, 413-455, 1950。Coxeter, H. S. M.; Frucht, R.; 和 Powers, D. L. 零对称图：群的三价图正则表示。 纽约：学术出版社，1981 年。Foster, R. M. “电气网络的几何电路。”美国电气工程师学会学报 51, 309-317, 1932。Frucht, R. “一个三度的单正则图。”加拿大数学杂志 4, 240-247, 1952。Harary, F. 图论。 马萨诸塞州雷丁：Addison-Wesley，第171-175 页，1994 年。Pegg, E. Jr. “数学游戏：三次对称图。”2003 年 12 月 30 日。http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html。Read, R. C. 和 Wilson, R. J. 图集。 英国牛津：牛津大学出版社，1998 年。Royle, G. “三次对称图（福斯特普查）。”http://school.maths.uwa.edu.au/~gordon/remote/foster/#census。Royle, G. “浏览图表。”http://school.maths.uwa.edu.au/~gordon/remote/foster/tables.html。Sloane, N. J. A. 在“整数序列在线百科全书”中的序列 A059282，A075124 和 A091430。Wolfram, S. 一种新的科学。 伊利诺伊州香槟：Wolfram Media，第 1032 页，2002 年。

在 Wolfram|Alpha 上引用

三次对称图

引述本文

Weisstein, Eric W. “三次对称图。”来自MathWorld——Wolfram 网络资源。https://mathworld.net.cn/CubicSymmetricGraph.html

学科分类