主題
Search

Higman-Sims 圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
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_i 和 v_j 的交集為空時，在 v in V 中的 v 之間構造 616 條邊；當 j 是 v_i 的成員時，在 v_i 和 p_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 設計

使用 探索

參考文獻

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 圖。" 來自 -- 資源。 https://mathworld.tw/Higman-SimsGraph.html

主題分類