TOPICS
Search

Desargues Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
DesarguesGraph

The Desargues graph is the cubic symmetric graph on 20 vertices and 30 edges illustrated above in several embeddings. It is isomorphic to the generalized Petersen graph GP(10,3) and to the bipartite Kneser graph H(5,2). It is the Levi graph of the Desargues configuration. It can be represented in LCF notation as [5,-5,9,-9]^5 (Frucht 1976). It can also be constructed as the graph expansion of 10P_2 with steps 1 and 3, where P_2 is a path graph. It is distance-transitive and distance-regular graph and has intersection array {3,2,2,1,1,;1,1,2,2,3}.

The Desargues graph is one of three cubic graphs on 20 nodes with smallest possible graph crossing number of 6 (the others being two unnamed graphs denoted CNG 6B and CNG 6C by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).

The Desargues is an integral graph with graph spectrum (-3)^1(-2)^4(-1)^51^52^43^1. It is cospectral with another nonisomorphic graph (Haemers and Spence 1995, van Dam and Haemers 2003).

It is also a unit-distance graph (Gerbracht 2008) and is 3-unitransitive (Harary 1994, p. 175).

The Desargues graph is the first of four graphs depicted on the cover of Harary (1994).

This graph is implemented in the Wolfram Language as GraphData["DesarguesGraph"].

See also

Cubic Symmetric Graph, Distance-Regular Graph, Distance-Transitive Graph, Smallest Cubic Crossing Number Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Desargues Graph." http://www.win.tue.nl/~aeb/drg/graphs/Desargues.html.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.DistanceRegular.org. "Desargues graph =D(O_3)." http://www.distanceregular.org/graphs/desargues.html.Frucht, R. "A Canonical Representation of Trivalent Hamiltonian Graphs." J. Graph Th. 1, 45-60, 1976.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Kagno, I. N. "Desargues' and Pappus' Graphs and Their Groups." Amer. J. Math. 69, 859-863, 1947.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Royle, G. "F020B." http://www.csse.uwa.edu.au/~gordon/foster/F020B.html.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs." http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

Cite this as:

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

Subject classifications