Sylvester graph

There is a unique distance-regular graph with intersection array {5,4,2;1,1,4}. It has 36 vertices and spectrum 5¹ 2¹⁶ (–1)¹⁰ (–3)⁹. It is known as Sylvester's double six graph.

Group

The full group of automorphisms is Aut S₆ with point stabilizer AGL(1,5)×2.

Construction

This is the graph on the 36 interior points of PG(2,9) with a conic, adjacent when orthogonal. (This shows the full group PGammaO(3,9).)

This is also the graph on the 36 words of weight 6 starting with 1 in perfect ternary Golay code, where two such words are adjacent when their Hamming distance is 9.

This is also the graph induced on the 36 vertices far away from an edge in the Hoffman-Singleton graph.

This is also the graph on the 36 pairs (ovoid,spread) in GQ(2,2), where (O,S) is adjacent to (O',S') when the unique point in both O and O' lies on the unique line in both S and S'.

The distance-3 graph is the 6×6 grid.

Supergraphs

The Sylvester graph is the subgraph of the Hoffman-Singleton graph consisting of the vertices at distance 2 from an edge.

Since the Higman-Sims graph can be split into two copies of the Hoffman-Singleton graph and the Gewirtz graph is the graph consisting of the vertices at distance 2 from an edge in the Higman-Sims graph, it follows that the Sylvester graph is also a subgraph of the Gewirtz graph.

The Sylvester graph is also a subgraph of the Cameron graph

Subgraphs

Maximal cocliques:

size #
 6: 12
 9: 1540
10: 5112
11: 720
12: 60

Of the 1540 maximal 9-cliques, 400 occur in a partition of the pointset into four maximal 9-cliques (each in ten such partitions), and there are 1000 such partitions. Of those 400, 40 meet the maximal 6-cocliques in either 0 or 3 (form a 3×3 grid) and 360 have intersections of sizes 0 (4×) 1 (2×) 2 (2×) 3 (4×).

Substructures belonging to the maximal subgroups of the automorphism group:

a) A partition of the vertex set into four 9-cocliques of 3×3 type. There are 10 of these, forming a single orbit. The stabilizer of one is 3²:D₈, with vertex orbit size 36. (A partition of the 6×6 grid into four 3×3 grids inducing cocliques.) In the PG(2,9) model, these are the points of the conic.

b) A maximal 6-coclique. There are 12 of these, forming a single orbit. The stabilizer of one is S₅, with vertex orbit sizes 6+30. (These are the grid lines - cliques in the distance-3 graph.) In the PG(2,9) model, these are the icosahedrals.

c) A pair of 12-cocliques. There are 30 of these, forming a single orbit. The stabilizer of one is S₄ × 2 with vertex orbit sizes 12+24. The subgraph induced on the 12 is 6K₂. The subgraph induced on the 24 is cubic of girth 6. Given a 12-coclique C, the remaining 24 vertices split into 12 vertices with two neighbours in C and 12 vertices with three neighbours in C, and the latter again form a 12-coclique. (These are the pairs of parallel grid lines.) In the PG(2,9) model, these are the orthonormal bases. The graph induced on them by having nonempty intersection is the unique generalized octagon GO(1,2), the incidence graph of GQ(2,2).

d) A vertex. There are 36 of these, forming a single orbit. The stabilizer of one is 10:4 with vertex orbit sizes 1+5+20+10. In the PG(2,9) model, these are the interior points.

e) A pair of edges at distance 3. There are 45 of these, forming a single orbit. The stabilizer of one has order 2⁵ with vertex orbit sizes 2+8+8+8+8+2. (These are grid squares that induce 2K₂.) In the PG(2,9) model, these are the exterior points. The graph induced on them by the orthogonality relation is the unique generalized octagon GO(2,1).

References

[BCN], Section 13.1A.