| Shrikhande graph | |
| Vertices: | 16 |
| Edges: | 48 |
| Chromatic Number: | 4 |
| Chromatic Index: | 6 |
| Automorphisms: | 192 |
| Diameter: | 2 |
| Radius: | 2 |
| Girth: | 3 |
| Properties: | Strongly regular Hamiltonian Symmetric Eulerian Integral |
| Book Thickness: | 4 |
| Queue Number: | 3 |
In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959.[1] It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.
The Shrikhande graph can be constructed as a Cayley graph. The vertex set is
Z4 x Z4
\{\pm(1,0),\pm(0,1),\pm(1,1)\}
In the Shrikhande graph, any two vertices I and J have two distinct neighbors in common (excluding the two vertices I and J themselves), which holds true whether or not I is adjacent to J. In other words, it is strongly regular and its parameters are:, i.e.,
λ=\mu=2
The Shrikhande graph is locally hexagonal; that is, the neighbors of each vertex form a cycle of six vertices. As with any locally cyclic graph, the Shrikhande graph is the 1-skeleton of a Whitney triangulation of some surface; in the case of the Shrikhande graph, this surface is a torus in which each vertex is surrounded by six triangles.[3] Thus, the Shrikhande graph is a toroidal graph. The embedding forms a regular map in the torus, with 32 triangular faces. The skeleton of the dual of this map (as embedded in the torus) is the Dyck graph, a cubic symmetric graph.
The Shrikhande graph is not a distance-transitive graph. It is the smallest distance-regular graph that is not distance-transitive.[4]
The automorphism group of the Shrikhande graph is of order 192. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Shrikhande graph is a symmetric graph.
The characteristic polynomial of the Shrikhande graph is :
(x-6)(x-2)6(x+2)9
It has book thickness 4 and queue number 3.[5]