Gray graph
From Wikipedia, the free encyclopedia
| Gray graph | |
 |
|
| Named after | Marion Cameron Gray |
|---|---|
| Vertices | 54 |
| Edges | 81 |
| Girth | 8 |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Properties | Cubic Semi-symmetric |
In 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 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 (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 (Marušič, Pisanski & Wilson 2005).
[edit] References
- Bouwer, I. Z. (1968), “An edge but not vertex transitive cubic graph”, Bulletin of the Canadian Mathematical Society 11: 533–535
- Bouwer, I. Z. (1972), “On edge but not vertex transitive regular graphs”, Journal of Combinatorial Theory, Series B 12: 32–40
- Marušič, Dragan & Pisanski, Tomaž (2000), “The Gray graph revisited”, Journal of Graph Theory 35: 1–7
- Marušič, Dragan; Pisanski, Tomaž & Wilson, Steve (2005), “The genus of the Gray graph is 7”, European Journal of Combinatorics 26 (3–4): 377–385, DOI 10.1016/j.ejc.2004.01.015
