The Gray graph is a cubic semisymmetric graph on 54 vertices. It was discovered by Marion C. Gray in 1932, and was first published
by Bouwer (1968). Malnič et al. (2002) showed that the Gray graph is
indeed the smallest possible cubic semisymmetric
graph.
The Gray graph has a single order-9 LCF notation and five distinct
order-1 LCF notations.
The Gray graph has girth 8, graph diameter 6, automorphism group order , and is the Levi
graph of two dual, triangle-free, point-, line-, and flag-transitive, non-self-dual
configurations
(Marušič and Pisanski 2000). The symmetric embedding illustrated above
is due to (Marušič and Pisanski 2000). The Gray graph is implemented
in the Wolfram Language as GraphData["GrayGraph"].
The Gray graph can be constructed by taking three copies of the complete bipartite graph
and, for a particular edge ,
subdividing
in each of the three copies, joining the resulting three vertices to a new vertex,
and repeating with each edge.
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 235, 1976.Bouwer,
I. Z. "An Edge but Not Vertex Transitive Cubic Graph." Bull. Canad.
Math. Soc.11, 533-535, 1968.Bouwer, I. Z. "On
Edge but Not Vertex Transitive Regular Graphs." J. Combin. Th. B12,
32-40, 1972.Brouwer, A. E. "Gray Graph." http://www.win.tue.nl/~aeb/drg/graphs/Gray.html.Malnič,
A.; Marušič, D.; Potočnik, P.; and Wang, C. "An Infinite Family
of Cubic Edge- but Not Vertex-Transitive Graphs." Discr. Math.280,
133-148, 2002.Marušič, D. and Pisanski, T. "The Gray
Graph Revisited." J. Graph Th.35, 1-7, 2000.Marušič,
D.; Pisanski, T.; and Wilson, S. "The Genus of the GRAY [sic] Graph is 7."
Europ. J. Combin.26, 377-385, 2005.Pisanski, T. and Randić,
M. "Bridges between Geometry and Graph Theory." In Geometry
at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini).
Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Weisstein,
E. W. "The Gray Graph is the Smallest Graph of Its Kind." MathWorld
Headline News, Apr. 9, 2002. http://mathworld.wolfram.com/news/2002-04-09/graygraph/.
![[-25,7,-7,13,-13,25]^9](/images/equations/GrayGraph/Inline1.svg)
and five distinct
order-1 LCF notations.
, and is the Levi
graph of two dual, triangle-free, point-, line-, and flag-transitive, non-self-dual
configurations
(Marušič and Pisanski 2000). The symmetric embedding illustrated above
is due to (Marušič and Pisanski 2000). The Gray graph is implemented
in the Wolfram Language as GraphData["GrayGraph"].
and, for a particular edge 
,
subdividing 
in each of the three copies, joining the resulting three vertices to a new vertex,
and repeating with each edge.
