Up
# Shrikhande graph

*The Shrikhande graph (drawn on a torus)*.

Sharad-Chandra S. Shrikhande showed in
*The uniqueness of the L*_{2} association scheme,
Ann. Math. Statist. **30** (1959) 781-798,
that strongly regular graphs with the parameters of a lattice graph
H(2,*n*) are isomorphic to H(2,*n*), except for *n* = 4,
where there is a unique other graph, known as the *Shrikhande graph*.
The parameters are *v* = 16, *k* = 6, λ = 2, μ = 2.
The spectrum is 6^{1} 2^{6} (−2)^{9}.

This graph is a (0,2)-graph.

This graph is locally a hexagon. (And consequently is a quotient
of the plane triangular lattice.)

This graph is obtained from the 4x4 lattice graph by switching
with respect to a 4-coclique or an 8-circuit.

This graph is the complement of the Latin square graph for the
cyclic Latin square of order 4.

The group of automorphisms has order 192, and is sharply transitive
on ordered triangles. It is rank 4: two vertices can be identical,
or adjacent, or nonadjacent where the two common neighbours form an edge,
or a nonedge.

The bipartite double is the folded 6-cube, with automorphism group
of order 23040 = 2^{5}.6!. The folded 6-cube is also
the bipartite double of the 4x4 lattice graph H(2,4).

The graph that has the triangles of the Shrikhande graph as vertices,
adjacent when they share an edge, is the Dyck graph.

## Independence and chromatic number

The Shrikhande graph has independence number 4 and chromatic number 4.
The complement of the Shrikhande graph has independence number 3
and chromatic number 6.

For comparison, the other graph with the same parameters
(called 4x4 or H(2,4) or L_{2}(4)) has independence
and chromatic number 4, like the Shrikhande graph, and also its
complement has independence and chromatic number 4.
Thus, the complement of the 4x4 grid graph and the complement
of the Shrikhande graph are strongly regular graphs with the same
parameters but different independence and chromatic number.