en>Chris the speller: typos, replaced: non trivial → nontrivial (2), non compact → noncompact using AWB (8277)

2012-08-21T17:54:07Z

typos, replaced: non trivial → nontrivial (2), non compact → noncompact using AWB (8277)

New page

{{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]] [[Hamiltonian graph|Hamiltonian]] [[Symmetric graph|Symmetric]] [[Eulerian graph|Eulerian]] [[Integral graph|Integral]]
}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Shrikhande graph''' is a [[Gallery of named graphs|named 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|authorlink=S. S. Shrikhande|title=The uniqueness of the L2 association scheme|journal=Annals of Mathematical Statistics|volume=30|year=1959|pages=781–798|jstor=2237417}}.</ref> It is a [[strongly regular graph]] with 16 [[vertex (graph theory)|vertices]] and 48 [[edge (graph theory)|edges]], with each vertex having a [[degree (graph theory)|degree]] of 6.

==Construction==
The Shrikhande graph can be constructed as a [[Cayley graph]], where the vertex set is <math>\mathbb{Z}_4 \times \mathbb{Z}_4</math>, and where 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, its parameters for being strongly regular are: {16,6,2,2}, with <math>\lambda = \mu = 2</math>, this equality implying that the graph is associated with a [[symmetry|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. <ref name="s59"/><ref>{{citation|first=F.|last=Harary|authorlink=Frank Harary|title=Graph Theory|publisher=Addison-Wesley|location=Massachusetts|year=1972|url=http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf|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]] in which each vertex is surrounded by six triangles.<ref>[[Andries Brouwer|Brouwer, A. E.]] [http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html Shrikhande graph].</ref> 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.<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]].

The [[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]]: its [[Spectral graph theory|spectrum]] consists entirely of integers.

==Gallery==
<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 graph|Hamiltonian]].
</gallery>

==Notes==
{{reflist}}

==References==
*{{citation|first1=D. A.|last1=Holton|first2=J.|last2=Sheehan|title=The Petersen Graph|publisher=[[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], [[Peter Cameron (mathematician)|Peter Cameron]], August 2010.

[[Category:Individual graphs]]
[[Category:Regular graphs]]
[[Category:4-chromatic graphs]]

Nash functions - Revision history

en>Chris the speller: typos, replaced: non trivial → nontrivial (2), non compact → noncompact using AWB (8277)