Shrikhande graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Shrikhande graph
Shrikhande graph square.svg
The Shrikhande graph
Named after S. S. Shrikhande
Vertices 16
Edges 48
Radius 2
Diameter 2
Girth 3
Automorphisms 192
Chromatic number 4
Chromatic index 6
Properties Strongly regular
Hamiltonian
Symmetric
Eulerian
Integral

In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959.[1][2] It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having a degree of 6. Every pair of nodes has exactly two other neighbors in common, whether the pair of nodes is connected or not.

Construction[edit]

The Shrikhande graph can be constructed as a Cayley graph, where the vertex set is \mathbb{Z}_4 \times \mathbb{Z}_4, and where two vertices are adjacent if and only if the difference is in \{\pm( 1,0),\pm(0,1),\pm (1,1)\}.


Properties[edit]

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, 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. It shares these parameters with a different graph, the 4×4 rook's graph. The 4×4 square grid is the only square grid for which the parameters of the rook's graph are NOT unique, but are shared with a non-rook's graph, namely the Shrikhande graph. [2][3]

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.[4] Thus, the Shrikhande graph is a toroidal graph. The dual of this embedding 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.[5]

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. Therefore the Shrikhande graph is an integral graph: its spectrum consists entirely of integers.

Gallery[edit]

Notes[edit]

  1. ^ Weisstein, Eric W., "Shrikhande Graph", MathWorld.
  2. ^ a b Shrikhande, S. S. (1959), "The uniqueness of the L2 association scheme", Annals of Mathematical Statistics 30: 781–798, doi:10.1214/aoms/1177706207, JSTOR 2237417 .
  3. ^ Harary, F. (1972), "Theorem 8.7", Graph Theory, Massachusetts: Addison-Wesley, p. 79 .
  4. ^ Brouwer, A. E. Shrikhande graph.
  5. ^ Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), Distance-Regular Graphs, New York: Springer-Verlag, pp. 104–105 and 136 .

References[edit]

External links[edit]