The Hoffman-Singleton graph is the graph on 50 nodes and 175 edges that is the only regular graph of vertex
degree 7, diameter 2, and girth
5. It is the unique cage graph and Moore
graph , and contains many copies of the Petersen
graph . It can be constructed from the 10 5-cycles illustrated above, with vertex
Other constructions are given by Benson and Losey (1971) and Biggs (1993, p. 163). A beautiful symmetric embedding corresponding to an order-5 generalized LCF
notation is illustrated above.
The Hoffman-Singleton graph is a strongly regular graph with parameters integral
graph with graph spectrum automorphism
group is of order
It is distance-regular and distance-transitive with intersection array
The edge chromatic number of the Hoffman-Singleton
graph is 7 (Royle 2004).
The graph complement of the Hoffman-Singleton
graph is isomorphic to its distance 2-graph .
It has graph crossing number of no more than 860 (as determined using QuickCross; E. Weisstein, May 12, 2019) and a rectilinear
crossing number of no more than 872 (G. Exoo, pers. comm., May 12, 2019),
though the the actual regular and rectilinear crossing numbers are almost certainly
equal.
See also Cage Graph ,
Hoffman Graph ,
Hoffman-Singleton Theorem ,
Moore Graph ,
Petersen
Graph
Explore with Wolfram|Alpha
References Benson, C. T. and 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. Bondy,
J. A. and Murty, U. S. R. Graph
Theory with Applications. Brouwer,
A. E. "Hoffman-Singleton Graph." http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html . 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 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. and Royle, G. "The Hoffman-Singleton Graph." §5.9 in Algebraic
Graph Theory. 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. and 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?" GRAPHNET@istserv.nodak.edu
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.
Cite this as:
Weisstein, Eric W. "Hoffman-Singleton Graph."
From MathWorld https://mathworld.wolfram.com/Hoffman-SingletonGraph.html
Subject classifications More... Less...
-cage graph and Moore
graph, and contains many copies of the Petersen
graph. It can be constructed from the 10 5-cycles illustrated above, with vertex
of 
joined to vertex 
(mod 5) of 
(Robertson 1969; Bondy and Murty 1976, p. 239; Wong
1982). (Note the correction of Wong's 
to 
.)
. It is an integral
graph with graph spectrum 
. Its automorphism
group is of order 
(Hafner 2003).
.
