TOPICS
Search

McLaughlin Graph


The McLaughlin graph is a 112-regular graph on 275 nodes and 15400 edges that can be constructed from the Witt design. It is distance-regular with intersection array {118,81;1,56}. It is also distance-transitive.

The first (isomorphic to the generalized quadrangle GQ(3,9)) and second subconstituents of the McLaughlin graph are also distance-regular (DistanceRegular.org).

To construct the graph, use the Witt design to create a 276-node graph X that is not regular, but whose switching class is a regular two-graph. (Note that a two-graph is not a graph, but is equivalent to a switching class of graphs. Any one graph in the switching class determines the entire switching class.) The graph X has two types of vertex; the points of the Witt design, and the blocks of the Witt design. Two vertices x,y of X are adjacent if and only if one of the following conditions holds:

1. x is a point and y is a block not containing x

2. x and y are blocks that intersect in one point.

This yields a 276-vertex graph where each "point" vertex has degree 176 and each "block" vertex has degree 128.

It can also be constructed from the Leech lattice by starting with three lattice points that form the vertices of an isosceles triangle with side lengths of 2, 2, and sqrt(6), identifying the exactly 275 lattice points that are at distance 2 from each triangle vertex, and joining two points with an edge if they are separated by distance sqrt(6). The resulting graph is the McLaughlin graph (Conway and Sloane 1999, pp. 292-293; Gaucher 2013; Brouwer and van Maldeghem 2022, p. 338).

A regular two-graph has the property that if we take a graph in the switching class, then we can "switch off" any vertex Consider the vertex v corresponding to the point 0; then we can divide the remaining vertices into three sets: A is the 176 blocks that do not contain 0, B is the 22 other points {1,2,...,22}, and C is the 77 blocks that do contain 0.

The partition {v|A|B|C} is an equitable partition of the vertices of X. More precisely, straightforward(ish) counting tells us that

1. Vertex v is adjacent to 176 vertices in A, 0 in B, and 0 in C.

2. Any vertex in A is adjacent to vertex v, to 70 (other) vertices in A, 15 vertices in B and 42 vertices in C.

3. Any vertex in B is adjacent to 120 vertices in A, 0 vertices in B and 56 vertices in C.

4. Any vertex in C is adjacent to 96 vertices in A, 16 in B and 16 in C.

If we now switch on the neighborhood of v (which is the set A) then every edge between a neighbor of v and a non-neighbor of v becomes a non-edge, and vice-versa. The effect of this is that all the edges from A to v, A to B, A to C become non-edges and all non-edges from A to v, A to B, A to C become edges. In particular,

1. v becomes an isolated vertex (all edges between v and A are turned from edges to non-edges)

2. every vertex in A remains adjacent to 70 vertices in A, but now becomes adjacent to 22-15=7 vertices in B and 77-42=35 vertices in C.

3. every vertex in B becomes adjacent to 176-120=56 vertices in A, remains adjacent to 0 in B and remains adjacent to 56 in C.

4. every vertex in C becomes adjacent to 176-96=80 vertices in A and remains adjacent to 16 vertices in B and 16 vertices in C.

A quick calculation shows that the degree of each vertex in A is 70+7+35=112, the degree of each vertex in B is 56+56=112 and the degree of each vertex in C is 80+16+16=112. Thus if we throw away the vertex v, then what remains is the 112-regular McLaughlin graph on 276 vertices.

The McLaughlin graph has independence number 22 (Brouwer), 4050 maximum independent vertex sets (Brouwer), and 10596258 maximal independent vertex sets (R. Pratt, pers. comm., Dec. 11, 2011).


See also

Leech Lattice, Local McLaughlin Graph, McLaughlin Group, Witt Design

Portions of this entry contributed by Gordon Royle

Explore with Wolfram|Alpha

References

Brouwer, A. E. "The McLaughlin Graph." http://www.win.tue.nl/~aeb/graphs/McL.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "The Regular Two-Graph on 276 Vertices and the McLaughlin Graph." §11.4H in Distance-Regular Graphs. New York: Springer-Verlag, pp. 372-373, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.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.Brouwer, A. E. and van Maldeghem, H. "The McLaughlin Graph." §10.61 in Strongly Regular Graphs. Cambridge, England: Cambridge University Press, pp. 337-340, 2022.DistanceRegular.org. "1st Subconstituent of McLaughlin Graph." http://www.distanceregular.org/graphs/1sub-mclaughlingraph.html.DistanceRegular.org. "2nd Subconstituent of McLaughlin Graph." http://www.distanceregular.org/graphs/2sub-mclaughlingraph.html.DistanceRegular.org. "McLaughlin Graph." http://www.distanceregular.org/graphs/mclaughlingraph.html.Gaucher, A. P. "Leech Lattice." https://cp4space.hatsya.com/2013/09/12/leech-lattice/. Sep. 12, 2013.Godsil, C. and Royle, G. "The Two-Graph of 276 Vertices." §11.8 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 260-262, 2001.Goethals, J. M. and Seidel, J. J. "The Regular Graph of 276 Vertices." Discr. Math. 25, 257-268, 1982.McLaughlin, J. "A Simple Group of Order 898128000." In The Theory of Finite Groups (Ed. R. Brauer and C.-H. Sah). New York: Benjamin, pp. 109-111, 1969.Royle, G. "The McLaughlin Graph." http://www.csse.uwa.edu.au/~gordon/constructions/mclaughlin.Conway, J. H. and Sloane, N. J. A. Sphere Packings, Lattices and Groups, 3rd ed. New York: Springer-Verlag, 1999.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Cite this as:

Royle, Gordon and Weisstein, Eric W. "McLaughlin Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/McLaughlinGraph.html

Subject classifications