The Shrikhande graph is a strongly regular graph on 16 nodes. It is cospectral with the rook graph , so neither of the two is determined by spectrum.
The Shrikhande graph is the smallest distance-regular graph that is not distance-transitive (Brouwer et al. 1989, p. 136). It has intersection array .
The Shrikhande graph is implemented in the Wolfram Language as GraphData["ShrikhandeGraph"].
The Shrikhande graph has two generalized LCF notations of order 8, eleven of order 4, 53 of order 2, and 2900 of order 1. The graphs with LCF notations of orders four and eight are illustrated above.
The Shrikhande graph appears on the cover of the book Combinatorial Matrix Theory by Brualdi and Ryser (1991); illustrated above.
The plots above show the adjacency, incidence, and graph distance matrices for the Shrikhande graph.
It is an integral graph with graph spectrum .
The bipartite double graph of the Shrikhande graph is the Kummer graph.
The following table summarizes some properties of the Shrikhande graph.
property | value |
automorphism group order | 192 |
characteristic polynomial | |
chromatic number | 4 |
chromatic polynomial | ? |
claw-free | no |
clique number | 3 |
graph complement name | ? |
determined by spectrum | no |
diameter | 2 |
distance-regular graph | yes |
dual graph name | Dyck graph |
edge chromatic number | 6 |
edge connectivity | 6 |
edge count | 48 |
edge transitive | yes |
Eulerian | yes |
girth | 3 |
Hamiltonian | yes |
Hamiltonian cycle count | 562464 |
Hamiltonian path count | ? |
integral graph | yes |
independence number | 4 |
line graph | no |
line graph name | ? |
perfect matching graph | no |
planar | no |
polyhedral graph | no |
radius | 2 |
regular | yes |
square-free | no |
strongly regular parameters | |
symmetric | yes |
traceable | yes |
triangle-free | no |
vertex connectivity | 6 |
vertex count | 16 |
vertex transitive | yes |