Gray graph

infobox graph
name = Gray graph


image_caption =
namesake = Marion Cameron Gray
vertices = 54
edges = 81
girth = 8
chromatic_number = 2
chromatic_index = 3
properties = Cubic Semi-symmetricIn mathematics, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. Its description was first published by harvtxt|Bouwer|1968, who wrote that it had been discovered in 1932 by Marion Cameron Gray.

The Gray graph can be constructed from the 27 points of a 3×3×3 grid and the 27 axis-parallel lines through these points. This collection of points and lines forms a projective configuration, the "Gray configuration": each point has exactly three lines through it, and each line has exactly three points on it. The Gray graph is the Levi graph of this configuration; it has a vertex for every point and every line of the configuration, and an edge for every pair of a point and a line that touch each other harv|Bouwer|1972. There are symmetries of the Gray graph taking every edge to any other edge, but not taking every vertex to any other vertex: the vertices that correspond to points of the Gray configuration can only be symmetric to other vertices that correspond to points, and the vertices that correspond to lines can only be symmetric to other vertices that correspond to lines. Therefore, the Gray graph is a semi-symmetric graph, the smallest possible cubic semi-symmetric graph.

Marušič and Pisanski (2000) give several alternative methods of constructing the Gray graph. As with any bipartite graph, there are no odd-length cycles, and there are also no cycles of four or six vertices, so the girth of the Gray graph is 8. The simplest oriented surface on which the Gray graph can be embedded has genus 7 harv|Marušič|Pisanski|Wilson|2005.

References

* citation
last = Bouwer | first = I. Z.
title = An edge but not vertex transitive cubic graph
journal = Bulletin of the Canadian Mathematical Society
volume = 11
pages = 533–535
year = 1968

* citation
last = Bouwer | first = I. Z.
title = On edge but not vertex transitive regular graphs
journal = Journal of Combinatorial Theory, Series B
volume = 12
pages = 32–40
year = 1972

* citation
authorlink1 = Dragan Marušič | last1 = Marušič | first1 = Dragan
authorlink2 = Tomaž Pisanski | last2 = Pisanski | first2 = Tomaž
title = The Gray graph revisited
journal = Journal of Graph Theory
volume = 35
pages = 1–7
year = 2000

* citation
authorlink1 = Dragan Marušič | last1 = Marušič | first1 = Dragan
authorlink2 = Tomaž Pisanski | last2 = Pisanski | first2 = Tomaž
last3 = Wilson | first3 = Steve
title = The genus of the Gray graph is 7
journal = European Journal of Combinatorics
volume = 26
issue = 3–4
year = 2005
pages = 377–385
doi = 10.1016/j.ejc.2004.01.015

External links

*

* [http://mathworld.wolfram.com/news/2002-04-09/graygraph/ The Gray Graph Is the Smallest Graph of Its Kind] , from MathWorld.