Hoffman–Singleton graph
| Hoffman–Singleton graph | |
|---|---|
 | |
| Named after |
Alan J. Hoffman Robert R. Singleton |
| Vertices | 50 |
| Edges | 175 |
| Radius | 2 |
| Diameter | 2[1] |
| Girth | 5[1] |
| Automorphisms |
252,000 (PSU(3,52):2)[2] |
| Chromatic number | 4 |
| Chromatic index | 7[3] |
| Genus | 29[4] |
| Properties |
Strongly regular Symmetric Hamiltonian Integral Cage Moore graph |
In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1).[5] It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest order Moore graph known to exist.[6] Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.
Construction
Here are two constructions of the Hoffman–Singleton graph.[7]
Construction from pentagons and pentagrams
Take five pentagons Ph and five pentagrams Qi, so that vertex j of Ph is adjacent to vertices j-1 and j+1 of Ph and vertex j of Qi is adjacent to vertices j-2 and j+2 of Qi. Now join vertex j of Ph to vertex h·i+j of Qi. (All indices are modulo 5.)[7]
Construction from Fano planes
Any set of seven points (as abstract mathematical objects) can be made into a Fano plane by adding seven lines to them. The number of distinct ways to do this is 30 = 7!/168. Here 7! is the number of permutations of the seven points. 168 is the number of symmetries of the Fano plane, and therefore the number of permutations that preserve any given set of lines that form a Fano plane. Among these 30 different Fano planes on the same points, each subset of three points is used as a line in 6 out of 30 of the planes. For any one of these 30 Fano planes, there are 14 others that share at least one line with it. The same set of seven points also has 35 different three-element subsets ("triads"), counted by the binomial coefficient . The Hoffman-Singleton graph can then be built from two sets of vertices:
- one for each Fano plane in a set of 15 Fano planes formed by choosing one arbitrarily and selecting the 14 others that share a line with it, and
- one for each triad.
These vertices are connected by edges of two types:
- between each selected Fano plane and the 7 triads that correspond to its lines, and
- between triads with no point in common.[7]
Algebraic properties
The automorphism group of the Hoffman–Singleton graph is a group of order 252,000 isomorphic to PΣU(3,52) the semidirect product of the projective special unitary group PSU(3,52) with the cyclic group of order 2 generated by the Frobenius automorphism. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Hoffman–Singleton graph is a symmetric graph. The stabilizer of a vertex of the graph is isomorphic to the symmetric group S7 on 7 letters. The setwise stabilizer of an edge is isomorphic to Aut(A6)=A6.22, where A6 is the alternating group on 6 letters. Both of the two types of stabilizers are maximal subgroups of the whole automorphism group of the Hoffman–Singleton graph.
The characteristic polynomial of the Hoffman–Singleton graph is equal to . Therefore the Hoffman–Singleton graph is an integral graph: its spectrum consists entirely of integers.
Subgraphs
Using only the fact that the Hoffman–Singleton graph is a strongly regular graph with parameters (50,7,0,1), it can be shown that there are 1260 5-cycles contained in the Hoffman–Singleton graph.
Additionally, the Hoffman–Singleton graph contains 525 copies of the Petersen graph. Removing any one of these leaves a copy of the unique (6,5) cage.[8]
See also
Notes
- 1 2 Weisstein, Eric W. "Hoffman-Singleton Graph". MathWorld.
- ↑ Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
- ↑ Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004.
- ↑ Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.
- ↑ Brouwer, Andries E., Hoffman-Singleton graph.
- ↑ Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.
- 1 2 3 Baez, John (February 1, 2016), "Hoffman–Singleton Graph", Visual Insight, American Mathematical Society
- ↑ Wong, Pak-Ken. "On the uniqueness of the smallest graph of girth 5 and valency 6". Journal of Graph Theory. 3: 407–409. doi:10.1002/jgt.3190030413.
References
- Benson, C. T.; Losey, N. E. (1971), "On a graph of Hoffman and Singleton", Journal of Combinatorial Theory. Series B, 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
- Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, pp. 186 and 190, ISBN 0-521-43594-3.