Up

U3(3) graph

There is a unique rank 3 strongly regular graph Γ with parameters v = 36, k = 14, λ = 4, μ = 6. The spectrum is 141 221 (–4)14. This graph is not determined by srg parameters only (there are precisely 180 different graphs with these parameters). However, the graph is determined by srg parameters plus 2-rank.

Group

The full group of automorphisms is G = U3(3).2, acting rank 3, with point stabilizer L2(7).2.

Constructions

(For somewhat more detailed info, see the Hall-Janko graph of which this graph is the first subconstituent.)

Subhexagons of GH(2,2)

The G2(2) generalized hexagon with parameters GH(2,2) has 36 sub-GH(2,1)'s. Join two of these when they have 4 lines in common.

Spreads of bases

In the projective plane PG(2,9) provided with a nondegenerate hermitean form, one has a unital with 28 points, and 63 nonisotropic points. The plane has 63.6.1/6 = 63 orthogonal bases.

The set of 63 nonisotropic points of PG(2,9) has precisely 36 partitions into 21 bases, twelve on any given basis. Each partition meets 1, 14, 21 partitions in 21, 3, 9 bases, respectively.

Our graph is the graph on these 36 partitions where two are adjacent when they meet in 3 bases.

1+14+21

Take a vertex x, let its 14 neighbours be the seven points and seven lines of the Fano plane, where a point is adjacent to a line when they are not incident, and let the 21 nonneighbours of x be the 21 flags of the Fano plane, where two flags are adjacent when they have no element in common, but the point of one is on the line of the other (that is, the subgraph on these 21 is the distance-2 graph of the flag graph of the Fano plane), and finally the flag (p,L) is adjacent to the three points on L and the three lines on p. This is our graph.

Supergraphs

This graph is the first subconstituent of the Hall-Janko graph.

Semibiplane

The graph Γ is locally bipartite. Construct a graph on 72 vertices (x,M) where x is a vertex of Γ and M one bipartite half of the neighbours of x. Call (x,M) and (y,N) adjacent when x is in N and y in M. The resulting graph is a bipartite (0,2)-graph (that is, the incidence graph of a semibiplane) of diameter 5 and valency 7. Each vertex has distance 5 to a unique other point. Interchanging antipodes is not an automorphism, but identifying antipodes yields the graph Γ again. This graph has automorphism group U3(3).2 with point stabilizer L2(7). The orbit sizes are 1+7+21+7+7+21+7+1, with diagram
1 -- 7 -- 21 -- 21 -- 7 -- 1
           |     |
           7 --  7

Subgraphs

We give the substructures of Γ associated to the 4 maximal subgroups of G distinct from U3(3), sorted according to increasing orbit size.

a) A partition into 12 parallel triangles
Let us call two disjoint or equal triangles S, T in Γ "parallel" if each vertex of S has the same number of neighbours in T and each vertex of T has the same number of neighbours in S. Then each triangle in Γ determines a unique partition of the vertex set of Γ into 12 mutually parallel triangles. There are 28 of these partitions, forming a single orbit. In the representation in PG(2,9) with hermitean form, these are the isotropic points.

b) A vertex.
There are 36 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is L2(7):2 with vertex orbit sizes 1+14+21. The subgraph induced on the first subconstituent is the co-Heawood graph (the bipartite point-line nonincidence graph of the Fano plane). The subgraph induced on the second subconstituent is the distance-2 subgraph of the thin generalized hexagon GH(2,1), the flag graph of the Fano plane.

c) A 12-point subgraph isomorphic to the 2-coclique extension of 2×3.
There are 63 of these, forming a single orbit. The stabilizer of one is 4.S4:2 = 2+1+4.S3 with vertex orbit sizes 12+24. In the representation inside the generalized hexagon, these are the points of the generalized hexagon. In the representation in PG(2,9) with hermitean form, these are the nonisotropic points.

d) K4,4.
There are 63 of these, forming a single orbit. The stabilizer of one is 42:D12 with vertex orbit sizes 8+12+16. In the representation inside the generalized hexagon, these are the lines of the generalized hexagon. In the representation in PG(2,9) with hermitean form, these are the orthogonal bases.

2-Ranks

The adjacency matrices of Γ and its complement both have 2-rank 8. Peeters showed that both Γ and its complement are uniquely determined by their strongly regular graph parameters and 2-rank.

Local characterization

Γ is locally the co-Heawood graph (the bipartite point-line nonincidence graph of the Fano plane). Up to isomorphism, there are three graphs with this local structure: Γ on 36 points, a triple cover on 108 points, and one further graph on 48 points (Brouwer, Fon-der-Flaass & Shpectorov).

Cliques, cocliques and chromatic number

The maximal cliques have size 3 (since the local graph is bipartite) and form a single orbit under G. Above we saw that there are partitions into 12 triangles, so that the complementary graph has chromatic number 12. The maximal cocliques fall into two orbits: there are 72 7-cocliques (namely the parts of the bipartitions of the 36 local graphs) and 126 maximal 4-cocliques (namely the parts of the bipartitions of the 63 K4,4's). The chromatic number is 6.

References

A. E. Brouwer, D. G. Fon-der-Flaass & S. V. Shpectorov, Locally co-Heawood graphs, pp 59-68 in: Finite geometry and combinatorics - Proc. Deinze 1992, F. De Clerck et al. (eds.), LMS Lect. Note Ser. 191, Cambridge UP, 1993.

B. D. McKay & E. Spence, Classification of regular two-graphs on 36 and 38 vertices, Australasian J. Combinatorics 24 (2001) 293-300.

René Peeters, Uniqueness of strongly regular graphs having minimal p-rank, Lin. Alg. Appl. 226-228 (1995) 9-31.