Hoffman-Singleton Graph
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 
of 
joined to vertex
(mod 5) of 
(Robertson 1969;
Bondy and Murty 1976, p. 239; Wong 1982). (Note the correction of Wong's 
to 
.)
The Hoffman-Singleton graph is a strongly regular graph with parameters 
.
It is an integral graph with graph
spectrum 
. Its automorphism
group is of order 
(Hafner 2003).
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.
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.
SEE ALSO: Cage Graph,
Hoffman Graph,
Hoffman-Singleton Theorem,
Moore Graph,
Petersen
Graph
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. Cambridge, England: Cambridge University Press, 1993.
Bondy, J. A. and 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. 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.
Exoo, G. "The Hoffman-Singleton Graph." http://ginger.indstate.edu/ge/Graphs/.
Godsil, C. and 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. 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?"
[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.
CITE THIS AS:
Weisstein, Eric W. "Hoffman-Singleton Graph."
From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Hoffman-SingletonGraph.html
Contact the MathWorld Team
hoffman-singleton
graph
