TOPICS
Search

Clebsch Graph


ClebschGraph

The Clebsch graph, also known as the Greenwood-Gleason graph (Read and Wilson, 1998, p. 284) and illustrated above in a number of embeddings, is a strongly regular quintic graph on 16 vertices and 40 edges with parameters (nu,k,lambda,mu)=(16,5,0,2). In fact, it is the unique strongly regular graph with these parameters (Godsil and Royle 2001, p. 230). It is also distance-regular with intersection array {5,4;1,2}, as well being distance-transitive.

Note that Brouwer et al. (1989, pp. 104 and 224) confusingly use the term "Clebsch graph" to refer to the halved 5-cube graph, which is strongly regular on parameters (16,10,6,6).

It can be obtained from the 5-hypercube graph Q_5 by merging antipodal points (i.e., those at distance equal to the graph diameter of 5 away), making it the 5-folded cube graph. It can also be obtained from the tesseract graph Q_4 by adding edges connecting the antipodal points.

In addition to being isomorphic to the 5-folded cube graph, the Clebsch graph is also isomorphic to the 16-cyclotomic graph and 2-Keller graph.

The Clebsch graph is implemented in the Wolfram Language as GraphData["ClebschGraph"].

ClebschGraphLCF

The Clebsch graph has three distinct LCF notations of order 4, six of order 2, and 21 of order 1. Symmetric embeddings corresponding to the order-3 and 2 are illustrated above.

If a loop is added to each vertex, the resulting adjacency matrix is equivalent to a 2-(16,6,2) block design.

The Clebsch graph is nonplanar and Hamiltonian and has chromatic number 4.

ClebschGraphK16

Kalbfleisch and Stanton (1968) showed that in a 3-edge coloring of the complete graph K_(16) without monochromatic triangles, the subgraph induced by the edges of any one color is isomorphic to the Clebsch graph, as illustrated above.

The Clebsch graph is an integral graph and has graph spectrum (-3)^51^(10)5^1.

The bipartite double graph of the Clebsch graph is the hypercube graph Q_5.


See also

Cyclotomic Graph, Folded Cube Graph, Hypercube Graph, Integral Graph, Keller Graph, Kummer Graph, Strongly Regular Graph, Tesseract Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 242, 1976.Brouwer, A. E. "Clebsch Graph." http://www.win.tue.nl/~aeb/drg/graphs/Clebsch.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 104, 1989.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 652, 1996.DistanceRegular.org. "Clebsch Graph = Folded 5-Cube." http://www.distanceregular.org/graphs/clebsch.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Clebsch Graph, SRG(16,5,0,2)." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/clebsch.png.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 226-230, 2001.Kalbfleisch, J. and Stanton, R. "On the Maximal Triangle-Free Edge-Chromatic Graph in Three Colors." J. Combin. Th. 5, 9-20, 1968.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 284, 1998.

Cite this as:

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

Subject classifications