View source for Shrikhande graph

{{Short description|Undirected graph named after S. S. Shrikhande}}
{{infobox graph
 | name = Shrikhande graph
 | image = [[Image:Shrikhande graph square.svg|250px]]
 | image_caption = The Shrikhande graph
 | namesake = S. S. Shrikhande
 | vertices = 16
 | edges = 48
 | chromatic_number = 4
 | chromatic_index = 6
 | automorphisms = 192
 | diameter = 2
 | radius = 2
 | girth    = 3
 | properties = [[Strongly regular graph|Strongly regular]]<br>Hamiltonian<br>[[Symmetric graph|Symmetric]]<br>Eulerian<br>[[Integral graph|Integral]]
|book thickness=4|queue number=3}}

In the [[Mathematics|mathematical]] field of [[Graph theory|graph theory]], the '''Shrikhande graph''' is a [[Gallery of named graphs|graph]] discovered by S. S. Shrikhande in 1959.<ref>{{mathworld|urlname=ShrikhandeGraph|title=Shrikhande Graph}}</ref><ref name="s59">{{citation|first=S. S.|last=Shrikhande|title=The uniqueness of the L<sub>2</sub> association scheme|journal=Annals of Mathematical Statistics|volume=30|year=1959|pages=781–798|jstor=2237417|doi=10.1214/aoms/1177706207|doi-access=free}}.</ref> It is a [[Strongly regular graph|strongly regular graph]] with 16 [[Vertex (graph theory)|vertices]] and 48 edges, with each vertex having [[Degree (graph theory)|degree]]&nbsp;6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.

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

==Properties==
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 graph|strongly regular]] and its parameters are: {16,6,2,2}, i.e., <math>\lambda = \mu = 2</math>.  This equality implies that the graph is associated with a [[Symmetry|symmetric]] BIBD. The Shrikhande graph shares these parameters with exactly one other graph, the 4&times;4 [[Rook's graph|rook's graph]], i.e., the [[Line graph|line graph]] ''L''(''K''<sub>4,4</sub>) of the [[Complete bipartite graph|complete bipartite graph]] ''K''<sub>4,4</sub>. The latter graph is the only line graph ''L''(''K<sub>n,n</sub>'') for which the strong regularity parameters do not determine that graph uniquely but are shared with a different graph, namely the Shrikhande graph (which is not a rook's graph).<ref name="s59"/><ref>{{citation|first=F.|last=Harary|title=Graph Theory|publisher=Addison-Wesley|location=Massachusetts|year=1972|url=http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf|archive-url=https://web.archive.org/web/20131109064416/http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf|url-status=dead|archive-date=November 9, 2013|contribution=Theorem 8.7|page=79}}.</ref>

The Shrikhande graph is [[Neighbourhood (graph theory)|locally hexagonal]]; that is, the neighbors of each vertex form a [[Cycle graph|cycle]] of six vertices. As with any locally cyclic graph, the Shrikhande graph is the [[N-skeleton|1-skeleton]] of a [[Triangulation (topology)|Whitney triangulation]] of some surface; in the case of the Shrikhande graph, this surface is a [[Torus|torus]] in which each vertex is surrounded by six triangles.<ref>Brouwer, A. E. [http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html Shrikhande graph].</ref> Thus, the Shrikhande graph is a [[Toroidal graph|toroidal graph]]. The embedding forms a [[Regular map (graph theory)|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|distance-transitive graph]]. It is the smallest [[Distance-regular graph|distance-regular graph]] that is not distance-transitive.<ref>{{citation|last1=Brouwer|first1=A. E.|last2=Cohen|first2=A. M.|last3=Neumaier|first3=A.|title=Distance-Regular Graphs|location=New York|publisher=Springer-Verlag|pages=104–105 and 136|year=1989}}.</ref>

The [[Graph automorphism|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|symmetric graph]].

The [[Characteristic polynomial|characteristic polynomial]] of the Shrikhande graph is : <math>(x-6)(x-2)^6(x+2)^9</math>. Therefore, the Shrikhande graph is an [[Integral graph|integral graph]]: its [[Spectral graph theory|spectrum]] consists entirely of integers.

It has book thickness 4 and [[Queue number|queue number]] 3.<ref>Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018</ref>

==Gallery==
<gallery>
Image:Shrikhande torus.svg|The Shrikhande graph is a [[Toroidal graph|toroidal graph]].
Image:Shrikhande graph 4COL.svg |The [[Chromatic number|chromatic number]] of the Shrikhande graph is&nbsp;4.
Image:Shrikhande graph 6color edge.svg |The chromatic index of the Shrikhande graph is&nbsp;6.
Image:Shrikhande graph symmetrical.svg|The Shrikhande graph drawn symmetrically.
File:Shrikhande Lombardi.svg|The Shrikhande graph is Hamiltonian.
</gallery>

==Notes==
{{reflist}}

==References==
*{{citation|first1=D. A.|last1=Holton|first2=J.|last2=Sheehan|title=The Petersen Graph|title-link= The Petersen Graph |publisher={{wipe|Cambridge University Press}}|year=1993|isbn=0-521-43594-3|page=270}}.

==External links==
*[http://cameroncounts.wordpress.com/2010/08/26/the-shrikhande-graph/ The Shrikhande Graph], [[Biography:Peter Cameron (mathematician)|Peter Cameron]], August 2010.

[[Category:Individual graphs]]
[[Category:Regular graphs]]
[[Category:Strongly regular graphs]]

{{Sourceattribution|Shrikhande graph}}