Gray graph

From Wikipedia, the free encyclopedia

In mathematics, the Gray graph is the smallest cubic semi-symmetric graph. It has 54 vertices and girth 8. Its description was first published by Bouwer (1968), who wrote that it had been discovered in 1932 by Marion Cameron Gray.

Marušič and Pisanski (2000) give several alternative methods of constructing the Gray graph. It is bipartite, and forms the Levi graph of two dual projective configurations of type (27₃27₃), one of which can be realized in R³ as a 3×3×3 grid of 27 points and the 27 orthogonal lines through them (Bouwer 1972). Every automorphism of the Gray graph sends a vertex to another vertex on the same side of its bipartition. The simplest oriented surface on which the Gray graph can be embedded has genus 7 (Marušič et al 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.

[edit] External links

• Weisstein, Eric W., Gray Graph at MathWorld.

• The Gray Graph Is the Smallest Graph of Its Kind, from MathWorld.