Up

# Graph

There is a unique strongly regular graph Γ with parameters v = 275, k = 112, λ = 30, μ = 56. The spectrum is 1121 2252 (–28)22. The complementary graph has parameters v = 275, k = 162, λ = 105, μ = 81 and spectrum 1621 2722 (–3)252. Uniqueness is due to Goethals & Seidel (1975). For a detailed discussion see Brouwer & van Lint (1984).

## Group

The full group of automorphisms of Γ is G = McL.2 (of order 28.36.53.7.11) acting rank 3, with point stabilizer U4(3):2.

## Construction

A 22+77+176 construction is found by taking the Steiner system S(4,7,23) with 1+22 points and 253 = 77+176 blocks, where the first 77 are those containing the first point. Use p,B,C to denote one of the 22, 77, 176 objects, and let ~ denote adjacency. Make the 22 remaining points a coclique, let p ~ B when p is not in B, let B ~ B' when B,B' meet in 1 point, let p ~ C when p is in C, let B ~ C when B,C meet in 3 points, let C ~ C' when C,C' meet in 1 point. This yields Γ. The resulting partition is equitable with parameters (0,56,56), (16,16,80), (7,35,70).

The same construction in other words: Take the 23 points and 253 blocks of S(4,7,23), with points forming a coclique, p ~ B when p is not in B, and B ~ B' when B,B' meet in 1 point. This yields a graph on 276 vertices that is member of the switching class of a regular two-graph. Now switch one point isolated (and delete it) to get Γ. See also h) below.

## Subgraphs

We give the substructures of Γ associated to the 11 maximal subgroups of G not containing McL, sorted according to increasing orbit size.

a) Vertices. There are 275 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is U4(3):2 with vertex orbit sizes 1+112+162. The graphs induced on the first and second subconstituent are described separately.

b) 22-cocliques. There are 4050 of these, forming a single orbit. The stabilizer of one is M22 with vertex orbit sizes 22+77+176. The graph induced on the 77 is the M22-graph.

c) Pairs of Hoffman-Singleton graphs. Γ has an orbit of splits 50+50+175 where the 50's induce the Hoffman-Singleton graph and the 175 induces the graph on the edges of the Hoffman-Singleton graph, adjacent when they are disjoint and lie in the same pentagon. This latter graph is strongly regular with parameters (v,k,λ,μ) = (175,72,20,36). If one takes the union of the two 50's and switches on this split one obtains the Higman-Sims graph. The stabilizer of a split 50+50+175 is U3(5):2, where the outer 2 interchanges the two 50's. There are 7128 such splits. *** Other HoSi's in Γ? ***

d) 5-cliques. There are 15400 of these, forming a single orbit. The stabilizer of one is 3+1+4:4S5 with vertex orbit sizes 5+270.

e) Edges. There are 15400 of these, forming a single orbit. The stabilizer of one is 34:(M10 × 2) with vertex orbit sizes 2+30+81+162. The graph induced on the 81 is the VO4(3) graph.

f) Non-edges. There are 22275 of these, forming a single orbit. The stabilizer of one is L3(4):22 with vertex orbit sizes 2+56+105+112. The graph induced on the 56 (the common neighbours) is the Gewirtz graph.

g) Odd graphs. Γ contains an orbit of 22275 Odd graphs O4. The stabilizer of one is 2.S8 with vertex orbit sizes 35+240. There are other subgraphs O4 in Γ since the local graph also contains such graphs. *** Any further Odd subgraphs? ***

h) Maximal 7-cocliques. There are 44550 of these, forming a single orbit. The stabilizer of one is 24:A7 with vertex orbit sizes 7+16+112+140. The 16 here is a maximal 16-coclique. (This is what one gets from the regular two-graph construction after switching a block isolated and deleting it.)

i) Maximal 11-cocliques of the first kind. There are 113400 of these, forming a single orbit. Γ has three orbits of maximal 11-cocliques. The first has stabilizer 2 × M11, with vertex orbit sizes 11+22+110+132. The 11 is a maximal 11-coclique, the 22 a (nice) 11K2. (There is a unique nice 11K2 on each 2K2, but there are many others as well.) The other two orbits of maximal 11-cocliques have stabilizers of order 12 and 36, not transtive on the coclique.

j) Splits 125+150. Γ has an orbit of splits 125+150 with stabilizer 5+1+2:3:8:2 with vertex orbit sizes 125+150. The 125 induces a rank 5 strongly regular graph with parameters (v,k,λ,μ) = (125,52,15,26).

k) 3-Cocliques. There are 779625 of these, forming a single orbit. The stabilizer of one is 22+4:(S3×S3) with vertex orbit sizes 3+8+32+64+72+96. The orbit of size 8 induces a K4,4.

## Cliques

The largest cliques have size 5. At first sight it looks like Γ might be the collinearity graph of a partial geometry with 28 lines of size 5 on each point. However, this possibility has been ruled out by Östergård & Soicher (2016).

## Cocliques

The largest cocliques have size 22. Numbers of maximal cocliques of given size (with orbit sizes):
```7: 44550
10: 13721400 = 1247400 + 12474000
11: 199697400 = 113400 + 49896000 + 149688000
13: 43659000 = 6237000 + 37422000
16: 757350 = 44550 + 712800
22: 4050
```

The largest cocliques in the line graph have size 11 (and there are 254016000 of these, 181440 on each edge, 2240 on each pair of disjoint edges).

## Chromatic number

The complement of Γ has chromatic number 55. That is, Γ has a partition into 55 5-cliques. (Haemers & Tonchev)

## References

A. E. Brouwer & J. H. van Lint,
Strongly regular graphs and partial geometries,
pp 85-122 in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.), Academic Press, Toronto, 1984.

J.-M. Goethals & J. J. Seidel,
The regular two-graph on 276 vertices,
Discr. Math. 12 (1975) 143-158.

W. H. Haemers & V. D. Tonchev,