Up

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

Sharad-Chandra S. Shrikhande showed in The uniqueness of the L2 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 61 26 (−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 = 25.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 L2(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.