TOPICS
Search

Gray Graph


GrayGraph

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.

It is the Levi graph of the Gray configuration.

The Gray graph has a single order-9 LCF notation [-25,7,-7,13,-13,25]^9 and five distinct order-1 LCF notations.

The Gray graph has girth 8, graph diameter 6, automorphism group order |AutG|=1296, and is the Levi graph of two dual, triangle-free, point-, line-, and flag-transitive, non-self-dual 27_3 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 has graph spectrum

 (-3)^1(-sqrt(6))^6(-sqrt(3))^(12)0^(16)(sqrt(3))^(12)(sqrt(6))^63^1.

The Gray graph can be constructed by taking three copies of the complete bipartite graph K_(3,3) and, for a particular edge e, subdividing e in each of the three copies, joining the resulting three vertices to a new vertex, and repeating with each edge.


See also

Complete Bipartite Graph, Cubic Graph, Cubic Semisymmetric Graph, Edge-Transitive Graph, Folkman Graph, Iofinova-Ivanov Graphs, Ljubljana Graph, Semisymmetric Graph, Symmetric Graph, Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

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. B 12, 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/.

Cite this as:

Weisstein, Eric W. "Gray Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GrayGraph.html

Subject classifications