- Higman–Sims graph
infobox graph
name = Higman–Sims graph
image_caption = Drawing based on Paul R. Hafner's construction.
namesake =Donald G. Higman Charles C. Sims
vertices = 100
edges =
chromatic_number =
chromatic_index =
properties = Strongly regular
The separated parts of Hafner's construction.In
mathematics , the Higman–Sims graph is the uniquestrongly regular graph with 100 vertices and valency 22, where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was constructed by Donald G. Higman and Charles C. Sims as a way to define theHigman–Sims group , and that group is a subgroup of index two in the group of automorphisms of the Higman–Sims graph.Construction begins with the M22 graph, whose 77 vertices are the blocks of the S(3,6,22)
Steiner system W22. Adjacent vertices are defined to be disjoint blocks. This graph is strongly regular; any vertex has 16 neighbors, any 2 adjacent vertices have no common neighbors, and any 2 non-adjacent vertices have 4 common neighbors. This graph has M22:2 as its automorphism group, M22 being aMathieu group .The Higman–Sims graph is then formed by appending the 22 points of W22 and a 100th vertex C. The neighbors of C are defined to be those 22 points. A point adjacent to a block is defined to be one that is included.
A Higman–Sims graph can be partitioned into 2 copies of the
Hoffman-Singleton graph and there are 352 ways to do this.References
*citation
last1 = Higman | first1 = Donald G. | authorlink = Donald G. Higman
last2 = Sims | first2 = Charles C.
title = A simple group of order 44,352,000
journal =Mathematische Zeitschrift
volume = 105 | issue = 2 | year = 1968 | pages = 110–113
doi = 10.1007/BF01110435.*citation
last1 = Hafner | first1 = P. R.
title = [http://www.combinatorics.org/Volume_11/PDF/v11i1r77.pdf On the Graphs of Hoffman-Singleton and Higman-Sims]
journal = [http://www.combinatorics.org The Electronic Journal of Combinatorics]
volume = 11 | issue = 1 | year = 2004 | pages = R77(1-32) .External links
* cite web
url = http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html
title = Higman-Sims graph
author = Brouwer, Andries E.*
Wikimedia Foundation. 2010.