View source for Gray graph

{{infobox graph
 | name = Gray graph
 | image = [[Image:Gray graph hamiltonian.svg|240px]]
 | image_caption = The Gray graph
 | namesake = [[Marion Cameron Gray]]
 | vertices = 54
 | edges = 81
 | girth = 8
 | diameter = 6
 | radius = 6
 | genus = 7
 | chromatic_number = 2
 | chromatic_index = 3
 | automorphisms = 1296
 | properties = [[Cubic graph|Cubic]]<br>[[Semi-symmetric graph|Semi-symmetric]]<br>[[Hamiltonian graph|Hamiltonian]]<br>[[Bipartite graph|Bipartite]]
|book thickness=3|queue number=2}}
In the [[mathematics|mathematical]] field of [[graph theory]], the '''Gray graph''' is an [[undirected graph|undirected]] [[bipartite graph]] with 54 [[vertex (graph theory)|vertices]] and 81 [[edge (graph theory)|edges]]. It is a [[cubic graph]]: every vertex touches exactly three edges. It was discovered by [[Marion Cameron Gray|Marion C. Gray]] in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by [[Jon Folkman]] 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive (see below).

The Gray graph has [[chromatic number]] 2, [[chromatic index]] 3, radius 6 and diameter 6. It is also a 3-[[k-vertex-connected graph|vertex-connected]] and 3-[[k-edge-connected graph|edge-connected]] [[planar graph|non-planar graph]].

==Construction==
{{multiple image
|total_width=720
|image1=Gray configuration.svg
|caption1=3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3 grid whose point-line incidences are described by the Gray graph
|image2=Gray graph.svg
|caption2=Graph with vertices arranged and colored by their position in the grid
|image3=Gray UD.pdf
|caption3=Graph as a unit-distance graph with 3-fold rotational symmetry
}}
The Gray graph can be constructed {{harv|Bouwer|1972}} from the 27 points of a 3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3 grid and the 27 axis-parallel lines through these points. This collection of points and lines forms a [[projective 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. This construction generalizes (Bouwer 1972) to any dimension ''n'' ≥ 3, yielding an ''n''-valent Levi graph with algebraic properties similar to those of the Gray graph. In (Monson, Pisanski, Schulte, Ivic-Weiss 2007), the Gray graph appears as a different sort of Levi graph for the edges and triangular faces of a certain locally toroidal abstract regular 4-polytope. It is therefore the first in an infinite family of similarly constructed cubic graphs. As with other Levi graphs, it is a [[bipartite graph]], with the vertices corresponding to points on one side of the bipartition and the vertices corresponding to lines on the other side.

[[Dragan Marušič|Marušič]] and [[Tomaž Pisanski|Pisanski]] (2000) give several alternative methods of constructing the Gray graph. As with any bipartite graph, there are no odd-length [[cycle (graph theory)|cycles]], and there are also no cycles of four or six vertices, so the [[girth (graph theory)|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}}.

The Gray graph is [[Hamiltonian graph|Hamiltonian]] and can be constructed from the [[LCF notation]]:
:<math>[-25,7,-7,13,-13,25]^9.\ </math>
As a Hamiltonian cubic graph, it has [[chromatic index]] three.

==Algebraic properties==
The [[automorphism group]] of the Gray graph is a group of order 1296. It acts transitively on the edges the graph but not on its vertices: there are [[Graph automorphism|symmetries]] taking every edge to any other edge, but not taking every vertex to any other vertex. The vertices that correspond to points of the underlying 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.

The characteristic polynomial of the Gray graph is
:<math>(x-3) x^{16} (x+3) (x^2-6)^6 (x^2-3)^{12}.\ </math>

==Geometric properties==
The Gray graph can be represented by points in the plane in such a way that adjacent vertices are at unit distance apart; that is, it is a [[unit distance graph]].
<ref>{{cite arXiv|title=The Gray graph is a unit-distance graph|last1=Berman|first1=Leah|last2=Gévay|first2=Gábor|last3=Pisanski|first3=Tomaž|author3-link=Tomaž Pisanski|eprint = 2312.15336|date=2023|class=math.CO }}.</ref>

== References ==
{{reflist}}
* {{citation
  | last = Bouwer | first = I. Z.
  | title = An edge but not vertex transitive cubic graph
  | journal = [[Canadian Mathematical Bulletin]]
  | volume = 11
  | pages = 533–535
  | year = 1968
  | issue = 4
  | doi = 10.4153/CMB-1968-063-0 | doi-access = free}}. (Izak Zurk Bouwer (1933–2012) was a [[University of New Brunswick|UNB]] professor. {{cite news|title=Obituary. Izak Bouwer|newspaper=Ottawa Citizen|date=December 28, 2012|url=https://ottawacitizen.remembering.ca/obituary/izak-bouwer-1065933615}})
* {{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
  | doi = 10.1016/0095-8956(72)90030-5 | doi-access = 
  }}.
* {{citation
 | last = Folkman | first = J. | authorlink = Jon Folkman
 | title = Regular line-symmetric graphs
 | journal = [[Journal of Combinatorial Theory]]
 | volume = 3
 | pages = 533–535
 | year = 1967
 | doi = 10.1016/S0021-9800(67)80069-3
 | issue = 3 | doi-access = free
 }}.
* {{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
  | doi = 10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7}}.
* {{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| doi-access = free
  }}.
*{{citation
 | last1 = Monson | first1 = B.
 | last2 = Pisanski | first2 = T. | author2-link = Tomaž Pisanski
 | last3 = Schulte | first3 = E.
 | last4 = Ivic-Weiss | first4 = A.
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 421–435
 | title = Semisymmetric Graphs from Polytopes
 | volume = 114
 | year = 2007
 | doi = 10.1016/j.jcta.2006.06.007 | doi-access=free
 | issue = 3| arxiv = math/0606469
 | s2cid = 10203794
 }}

{{clear left}}

== External links ==

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

[[Category:Configurations (geometry)]]
[[Category:Individual graphs]]
[[Category:Regular graphs]]