主题
Search

霍夫曼-辛格尔顿图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
HoffmanSingletonGraph

霍夫曼-辛格尔顿图是一个具有 50 个节点和 175 条边的图，它是唯一的正则图，具有顶点度 7，直径 2 和围长 5。它是唯一的 (7,5)-笼形图 和 穆尔图，并包含许多 彼得森图 的副本。它可以由上面示出的 10 个 5-环构成，其中 i 的顶点 P_j 连接到 i+jk (mod 5) 的顶点 Q_k (Robertson 1969; Bondy 和 Murty 1976, p. 239; Wong 1982)。（注意 Wong 的 j+jk 更正为 i+jk。）

HoffmanSingletonSymmetric

Benson 和 Losey (1971) 以及 Biggs (1993, p. 163) 给出了其他构造方法。上面展示了一个美丽的对称嵌入，它对应于 5 阶广义 LCF 符号。

霍夫曼-辛格尔顿图是一个 强正则图，参数为 (nu,k,lambda,mu)=(50,7,0,1)。它是一个 积分图，图谱 为 (-3)^(21)2^(28)7^1。其自同构群的阶数为 252000 (Hafner 2003)。

它是距离正则和距离传递的，交集数组为 {7,6;1,1}。

霍夫曼-辛格尔顿图的边色数为 7 (Royle 2004)。

霍夫曼-辛格尔顿图的图补与其距离 2-图同构。

它的图交叉数不超过 860（使用 QuickCross 确定；E. Weisstein，2019 年 5 月 12 日）和直线交叉数不超过 872（G. Exoo，私人通讯，2019 年 5 月 12 日），尽管实际的正则和直线交叉数几乎肯定相等。

另请参阅

笼形图, 霍夫曼图, 霍夫曼-辛格尔顿定理, 穆尔图, 彼得森图

使用 Wolfram|Alpha 探索

参考文献

Benson, C. T. 和 Losey, N. E. "On a Graph of Hoffman and Singleton." J. Combin. Th. Ser. B 11, 67-79, 1971.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 235, 1976.Brouwer, A. E. "Hoffman-Singleton Graph." http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html.Brouwer, A. E. 和 van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson 和 S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.DistanceRegular.org. "Cocliques in Hoffman-Singleton." http://www.distanceregular.org/graphs/cocliques-hoffmansingleton.html.DistanceRegular.org. "2nd Subconstituent of Holfman-Singleton [sic] Graph." http://www.distanceregular.org/graphs/hs-subconstit.html.DistanceRegular.org. "Hoffman-Singleton Graph." http://www.distanceregular.org/graphs/hoffmansingleton.html.Exoo, G. "The Hoffman-Singleton Graph." http://isu.indstate.edu/ge/Graphs/HOFFSING/.Godsil, C. 和 Royle, G. "The Hoffman-Singleton Graph." §5.9 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 92-94, 2001.Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.Hafner, P. R. "On the Graphs of Hoffman-Singleton and Higman-Sims." Elec. J. Combin. 11, R77, 1-32, 2004.Hoffman, A. J. 和 Singleton, R. R. "On Moore Graphs of Diameter Two and Three." IBM J. Res. Develop. 4, 497-504, 1960.Pegg, E. Jr. "Math Games: The Hoffman-Singleton Game." Nov. 1, 2004. http://www.maa.org/editorial/mathgames/mathgames_11_01_04.html.Robertson, N. Graphs Minimal Under Girth, Valency, and Connectivity Constraints. Dissertation. Waterloo, Ontario: University of Waterloo, 1969.Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" [email protected] posting. Sept. 28, 2004. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0409&L=graphnet&F=&S=&P=4981.Tonchev, V. D. "Binary Codes Derived from the Hoffman-Singleton and Higman-Sims Graphs." IEEE Trans. Info. Th. 43, 1021-1025, 1997.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

请引用为

Weisstein, Eric W. "霍夫曼-辛格尔顿图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Hoffman-SingletonGraph.html

主题分类