Up

Sims-Gewirtz graph

There is a unique strongly regular graph with parameters v = 56, k = 10, λ = 0, μ = 2. The spectrum is 101 235 (–4)20. This graph was found by Sims and studied by Gewirtz, who also proved uniqueness. It is commonly called the Gewirtz graph, or the Sims-Gewirtz graph.

Group

The full group of automorphisms is G = L3(4).22 (of order 28.32.5.7) acting rank 3, with point stabilizer A6.22. The eight different types of maximal subgroups of G are all recognized below as stabilizers of subgraphs.

Construction

The graph is the subgraph of the Higman-Sims graph induced on the set of vertices at distance 2 from two adjacent vertices (and this construction shows the full group).

It can also be described as the graph on the 77–21 = 56 blocks of the (unique) Steiner system S(3,6,22) not containing a fixed symbol, adjacent when they are disjoint. Or, equivalently, as the graph on the 56 hyperovals from one L3(4) orbit in PG(2,4), adjacent when they are disjoint. Or again, equivalently, as the graph on the 56 octads that contain two given symbols a,b but not a third symbol c, where two octads are adjacent when they meet in just {a,b}.

Biplane

Adding an identity matrix to its adjacency matrix yields a biplane 2-(56,11,2).

Supergraphs

This graph is subgraph of the M22 graph on 77 vertices, the Higman-Sims graph on 100 vertices, the U4(3) graph on 112 vertices, the McL graph on 275 vertices and the G2(4) graph on 416 vertices.

Subgraphs

a) A vertex. There are 56 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is A6.22 with vertex orbit sizes 1+10+45.

b) An edge. There are 280 of these, forming a single orbit. The stabilizer of one is 32:Q8.2×2 with vertex orbit sizes 2+18+36. In PG(2,4) these can be identified with the unitals (AG(2,3) subplanes): the complement of the union of two disjoint hyperovals is a unital. The graph on the 280 edges, where two edges are adjacent when they are opposite edges of a quadrangle, is distance-transitive with intersection array {9,8,6,3;1,1,3,8} and spectrum 91 464 1105 (–3)90 (–5)20. Its automorphism group Aut (L3(4)) is three times larger than that of the Gewirtz graph. The uniqueness of this graph (given its parameters) was shown by Lambeck.

c) A 16-coclique. There are 42 of these, forming a single orbit. The stabilizer of one is 24.S5 with vertex orbit sizes 16+40. In the Higman-Sims graph these are visible as point neighbourhoods. Also in PG(2,4) these 16-cocliques are visible: each point is in 16 of our hyperovals, and these hyperovals are mutually nonadjacent. Moreover, each hyperoval has six exterior lines forming a dual hyperoval, and disjoint hyperovals have disjoint dual hyperovals; it follows that the 21 lines of PG(2,4) also give 16-cocliques. The graph on the 16-cocliques, adjacent when disjoint, is the point-line incidence graph of PG(2,4). Distance 0,1,2,3 in this graph corresponds to an intersection of size 16,0,4,6, respectively.

d) 6 C4. There are 105 of these, forming a single orbit. The stabilizer of one is 22+4.3.22 with vertex orbit sizes 24+32. Each quadrangle determines a unique subgraph 6 C4, and hence there are 105 such subgraphs. The complement of one is the bipartite point-block incidence graph of AG(2,4) from which a parallel class of lines has been removed. In particular, we find partitions of the Gewirtz graph into one subgraph 6 C4 and two 16-cocliques. This pair of 16-cocliques can be viewed as a flag in PG(2,4). There are no other regular subgraphs of valency 2 on 24 vertices.

e) 10 K2 and Sylvester. There are 112 of these, forming a single orbit. The stabilizer of one is M10 with vertex orbit sizes 20+36.

A hyperoval of a non-chosen orbit meets our hyperovals in 1 or 3 points; 20 in 3 (each triple occurs once) and 36 in 1. This induces a partition of the graph into two subgraphs, one isomorphic to 10 K2, the other to the Sylvester graph (distance-regular with intersection array {5,4,2;1,1,4} on 36 vertices).

A different way to see this is to look at the Higman-Sims graph. It has splits into two Hoffman-Singleton graphs. Choosing an edge in one of the Hoffman-Singleton graphs we find that the subgraph of the Higman-Sims graph far away from that edge is split into a Sylvester graph and a 10 K2.

A different way to see the presence of subgraphs 10 K2 is by looking at the generalized quadrangle GQ(3,9) on 112 vertices. It has splits into two Gewirtz graphs, and the ten lines on a point on one side meet the other side in 10 K2.

f) co-Heawood graph. (The co-Heawood graph is the point-line nonincidence graph of the Fano plane.) There are 120 of these, forming a single orbit. The stabilizer of one is L2(7):2×2 with vertex orbit sizes 7+7+42. Their presence can be seen from the M24 construction: if our Gewirtz graph consists of the octads starting 110, then fix an octad B starting 001. There are 7, 42, 7 octads in our graph that meet B in 4, 2, 0 vertices, respectively, and the 7+7 induces a co-Heawood graph. The involution in M24 that fixes B pointwise, and fixes the pair contained in all Gewirtz octads fixes the co-Heawood graph pointwise. There is no automorphism here interchanging the two 7-cocliques in the co-Heawood graph.

g) Splits into two Coxeter graphs. The Gewirtz graph has 240 splits into two Coxeter graphs, forming a single orbit. The stabilizer of one split is L2(7):2 with vertex orbit sizes 28+28.

These splits can be seen inside the Higman-Sims graph. It has splits into two Hoffman-Singleton graphs. Choosing an edge that meets both sides we find that the subgraph of the Higman-Sims graph far away from that edge is split into two Coxeter graphs.

A different way to see these is to look at the M24 construction: if our Gewirtz graph consists of the octads starting 110, then fix an octad B starting 100 or 010. There are 28, 28 octads in our graph that meet B in 3, 1 vertices, respectively, and thus each B gives a split.

h) Extended bipartite double of the Petersen graph. There are 336 of these, forming a single orbit. The stabilizer of one is S5×2 with vertex orbit sizes 6+20+30. The extended bipartite double of the Petersen graph has 20 vertices and spectrum 41 25 14 (–1)4 (–2)5 (–4)1. Inside the Higman-Sims graph it can be seen by taking a path a ~ b ~ c ~ d of length 3, and taking the 20 vertices adjacent to one of a, d and none of b, c.

p-rank

The adjacency matrix A of the Gewirtz graph has 2-rank 20, 5-rank 55, and p-rank 56 for all other p. The matrix A+I has 3-rank 20, 11-rank 55, and p-rank 56 for all other p.

Independence and chromatic number

The Gewirtz graph has independence number 16 and chromatic number 4. The complement of the Gewirtz graph has independence number 2 and chromatic number 28.

Cocliques

Maximal cocliques have sizes 7, 9, 10, 11, 12, 13 or 16. For the 16-cocliques, see c) above. For the 7-cocliques, see f) above.
size  #
7     240
9     2520
10    43960
11    20160
12    5460
13    1680
16    42
A colouring with 4 colours must use two disjoint 16-cocliques. The complement of their union is the union of six quadrangles, in particular bipartite. Any 2-colouring of this 6 C4 either determines two maximal 12-cocliques, or a maximal 12-coclique and a 16-coclique. See also d) above.

Cycles

This graph is Hamiltonian.

References

A. Gewirtz, Graphs with maximal even girth, Canad. J. Math. 21 (1969) 915-934.

A. Gewirtz, The uniqueness of g(2,2,10,56), Trans. New York Acad. Sci. 31 (1969) 656-675.

A.E. Brouwer & W.H. Haemers, The Gewirtz graph - an exercise in the theory of graph spectra, Europ. J. Comb. 14 (1993) 397-407.

E.W. Lambeck, The uniqueness of a distance-regular graph on 280 vertices, in: Contributions to the theory of distance regular graphs, Ph.D. Thesis, Techn. Univ. Eindhoven, Netherlands, 1990.