Shrikhande graph

infobox graph
name = Shrikhande graph


image_caption = The Shrikhande graph drawn symmetrically.
namesake = S. S. Shrikhande
vertices = 16
edges = 48
chromatic_number =
chromatic_index =
properties = Strongly regular

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 $lambda\; =\; mu\; =\; 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. Thus, the Shrikhande graph is a toroidal graph.

External links

*mathworld|urlname=ShrikhandeGraph|title=Shrikhande Graph
* [http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html Shrikhande graph embedded in a torus]

References

* D.A. Holton and J. Sheehan, "The Petersen graph", Cambridge University Press, 1993, ISBN 0-521-43594-3. Page 270.
* S.S. Shrikhande, "The uniqueness of the L₂ association scheme", "Ann .Math. Statist." 30 (1959) 781-798.