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(1,2)'s. Join two of these when they have 4 points 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.