Shrikhande graph

Construction

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

Properties

In the Shrikhande graph, any two distinct vertices I and J have two neighbors in common, which holds true whether or not I is adjacent to J. In other words, it is strongly regular and its parameters are {16, 6, 2, 2}, with \lambda = \mu = 2. This equality implies that the graph is associated with a symmetric BIBD. The Shrikhande graph shares these parameters with exactly one other graph, the 4×4 rook's graph, i.e., the line graph L(K4,4) of the complete bipartite graph K4,4. The latter graph is the only line graph L(Kn,n) for which the strong regularity parameters do not determine that graph uniquely but are shared with a different graph.

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. 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.

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.

It has book thickness 4 and queue number 3.

Gallery

Image:Shrikhande torus.svg|The Shrikhande graph is a toroidal graph. Image:Shrikhande graph 4COL.svg |The chromatic number of the Shrikhande graph is 4. Image:Shrikhande graph 6color edge.svg |The chromatic index of the Shrikhande graph is 6. Image:Shrikhande graph symmetrical.svg|The Shrikhande graph drawn symmetrically. File:Shrikhande Lombardi.svg|The Shrikhande graph is Hamiltonian.

Notes

References

• .

References

1. "Shrikhande Graph".
2. Shrikhande, S. S.. (1959). "The uniqueness of the L₂ association scheme". Annals of Mathematical Statistics.
3. Harary, F.. (1972). "Graph Theory". Addison-Wesley.
4. [[Andries Brouwer. Brouwer, A. E.]] [http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html Shrikhande graph].
5. (1989). "Distance-Regular Graphs". Springer-Verlag.
6. Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018