TOPICS
Search

Hoffman-Singleton Graph


HoffmanSingletonGraph

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 (7,5)-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 i of P_j joined to vertex i+jk (mod 5) of Q_k (Robertson 1969; Bondy and Murty 1976, p. 239; Wong 1982). (Note the correction of Wong's j+jk to i+jk.)

HoffmanSingletonSymmetric

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 (nu,k,lambda,mu)=(50,7,0,1). It is an integral graph with graph spectrum (-3)^(21)2^(28)7^1. Its automorphism group is of order 252000 (Hafner 2003).

It is distance-regular and distance-transitive with intersection array {7,6;1,1}.

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. 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.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. 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?" 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--A Wolfram Web Resource. https://mathworld.wolfram.com/Hoffman-SingletonGraph.html

Subject classifications