Gray graph

Gray graph
240px The Gray graph
Named after	Marion Cameron Gray
Vertices	54
Edges	81
Radius	6
Diameter	6
Girth	8
Automorphisms	1296
Chromatic number	2
Chromatic index	3
Properties	Cubic Semi-symmetric Hamiltonian Bipartite

In the mathematical field of graph theory, 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. It was discovered by 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-vertex-connected and 3-edge-connected non-planar graph.

Construction

The Gray graph can be constructed (Bouwer 1972) 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: 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.

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 (Marušič, Pisanski & Wilson 2005).

The Gray graph is Hamiltonian and can be constructed from the LCF notation:

$[-25,7,-7,13,-13,25]^9.\$

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

$(x-3) x^{16} (x+3) (x^2-6)^6 (x^2-3)^{12}.\$

Gallery

• 

  The Gray graph

• Gray graph 2COL.svg

  The chromatic number of the Gray graph is 2.

• Gray graph 3color edge.svg

  The chromatic index of the Gray graph is 3.

• Gray configuration.svg

  The underlying configuration of the Gray graph.

References

• .
• .
• .
• .
• .

External links

• Weisstein, Eric W., "Gray Graph", MathWorld.
• The Gray Graph Is the Smallest Graph of Its Kind, from MathWorld.