Shrikhande graph

From Wikipedia, the free encyclopedia

Shrikhande graph
The Shrikhande graph drawn symmetrically.
Named after	S. S. Shrikhande
Vertices	16
Edges	48
Properties	Strongly regular
This box: view • talk • edit

The Shrikhande graph is a named graph in graph theory, discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having a degree of 6. It has the property that 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, its parameters for being strongly regular are: {16,6,2,2}, with $λ = μ = 2$ , this equality implying that the graph is associated with a symmetric BIBD.

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.