主题
Search

Higman-Sims 图


Higman-SimsGraph

Higman-Sims 图是在 100 个节点上的唯一强正则图(Higman 和 Sims 1968,Brouwer 1983,Brouwer 和 Haemers 1993)。它也在 Goethals 和 Seidel(1970)的定理 5.3 中被独立构建。它具有正则参数 (nu,k,lambda,mu)=(100,22,0,6),其中 nu 是顶点数,k 是每个顶点的邻居数,lambda 是每对相邻顶点共享的公共邻居数,而 mu 是每对非相邻顶点共享的公共邻居数。

Higman-Sims 图是距离正则的,其相交数组{22,21;1,6}。它也是距离传递的。

它是一个积分图,其图谱(-8)^(22)2^(77)22^1

Higman-SimsGraphPieces

本文顶部给出的嵌入是由 Hafner (2004) 构建中产生的上面说明的十个图的图和

它可以通过从 Witt 设计中包含符号 1 的长度为 7 的 77 个向量开始构建,删除 1,并将剩余元素从 1 到 22 重新编号。将这些向量 V 视为顶点,并添加额外的 22 个顶点 P 和一个特殊顶点 Omega。现在,当 v_iv_j 的交集为空时,在 v in V 中的 v 之间构造 616 条边;当 jv_i 的成员时,在 v_ip_j 之间构造 462 条边;以及在 Omega 和每个 p_j 之间构造 22 条边。然后,在 100 个顶点和 1100 条边上的结果图就是 Higman-Sims 图。

Higman-Sims 图可以从 Hoffman-Singleton 图构建,方法是将后者的 100 个大小为 15 的独立顶点集视为顶点,并通过边连接那些恰好共享 0 或 8 个元素的独立集对。

它也可以从 Leech 格构建,方法是从形成等腰三角形顶点的三个格点开始,边长为 2、sqrt(6)sqrt(6),识别恰好距离每个三角形顶点距离为 2 的 100 个格点,如果两个点之间的距离为 sqrt(6),则用边连接这两个点。结果图是 Higman-Sims 图(Conway 和 Sloane 1999,第 292-293 页;Gaucher 2013;Brouwer 和 van Maldeghem 2022,第 303 页)。

Higman-Sims 图的自同构群在其边上是传递作用的(Brouwer 和 Haemers 1993)。

通过删除 Higman-Sims 图中一个点的邻居顶点而获得的图(正如 van Dam 和 Haemers 2003 所声称的,它不是由顶点邻居导出的子图)是 M22 图


另请参阅

Leech 格, M22 图, 强正则图, Witt 设计

使用 Wolfram|Alpha 探索

参考文献

Brouwer, A. E. "Higman-Sims Graph." http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html.Brouwer, A. E. "The Uniqueness of the Strongly Regular Graph of 77 Points." J. Graph Th. 7, 455-461, 1983.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 163 and 391, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397-407, 1993.Brouwer, A. E. and 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 and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brouwer, A. E. and van Maldeghem, H. "The Higman-Sims Graph." §10.31 in Strongly Regular Graphs. Cambridge, England: Cambridge University Press, pp. 303-304, 2022.Conway, J. H. and Sloane, N. J. A. Sphere Packings, Lattices and Groups, 3rd ed. New York: Springer-Verlag, 1999.DistanceRegular.org. "Higman-Sims Graph." http://www.distanceregular.org/graphs/higman-sims.html.Gaucher, A. P. "Leech Lattice." https://cp4space.hatsya.com/2013/09/12/leech-lattice/. Sep. 12, 2013.Gewirtz, A. "Graphs with Maximal Even Girth." Canad. J. Math. 21, 915-934, 1969.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.Hafner, P. R. "On the Graphs of Hoffman-Singleton and Higman-Sims." Elec. J. Combin. 11, R77, 1-32, 2004.Higman, D. G. and Sims, C. C. "A Simple Group of Order 44352000." Math. Z. 105 , 110-113, 1968.Tonchev, V. D. "Binary Codes Derived from the Hoffman-Singleton and Higman-Sims Graphs." IEEE Trans. Info. Th. 43, 1021-1025, 1997.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

请引用为

Weisstein, Eric W. "Higman-Sims 图。" 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/Higman-SimsGraph.html

主题分类