TOPICS
Search

Pappus Graph


PappusGraphEmbeddings

The Pappus graph is a cubic symmetric distance-regular graph on 18 vertices, illustrated above in three embeddings. It is Hamiltonian and can be represented in LCF notation as [5,7,-7,7,-7,-5]^3 (Frucht 1976). It is the Levi graph of the 9_3 configuration appearing in Pappus's hexagon theorem, namely the Pappus configuration. It is also Bouwer graph B(3,2,3) and honeycomb toroidal graph HTG(3,6,3).

The Pappus graph is one of two cubic graphs on 18 nodes with smallest possible graph crossing number of 5 (the other being an unnamed graph denoted CNG 5B by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).

PappusGraphUnitDistance

It is also a unit-distance graph, as illustrated in the above embedding (Gerbracht 2008; E. Gerbracht, pers. comm., Jan. 2, 2010).

PappusGraphMatrices

The plots above show the adjacency, incidence, and graph distance matrices for the Pappus graph.

The graph spectrum of the Pappus graph is (-3)^1(-sqrt(3))^60^4(sqrt(3))^63^1. The following table summarizes a number of properties of the Pappus graph.

propertyvalue
automorphism group order216
characteristic polynomial(x-3)x^4(x+3)(x^2-3)^6
chromatic number2
chromatic polynomial(x-1)x(x^(16)-26x^(15)+325x^(14)-2600x^(13)+14950x^(12)-65762x^(11)+229852x^(10)-653966x^9+1537363x^8-3008720x^7+4904386x^6-6609926x^5+7238770x^4-6236975x^3+3989074x^2-1690406x+356509)
claw-freeno
clique number2
graph complement name?
determined by spectrumyes
diameter4
distance-regular graphyes
dual graph name?
edge chromatic number3
edge connectivity3
edge count27
edge transitiveyes
Eulerianno
girth6
Hamiltonianyes
Hamiltonian cycle count72
Hamiltonian path count3024
integral graphno
independence number9
line graph?
line graph name?
perfect matching graphno
planarno
polyhedral graphno
radius4
regularyes
square-freeyes
symmetricyes
traceableyes
triangle-freeyes
vertex connectivity3
vertex count18
vertex transitiveyes
weakly regular parameters(18,(3),(0),(0,1))

See also

Cubic Symmetric Graph, Distance-Regular Graph, Honeycomb Toroidal Graph, Pappus Configuration, Pappus's Hexagon Theorem, Smallest Cubic Crossing Number Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Pappus Graph." http://www.win.tue.nl/~aeb/drg/graphs/Pappus.html.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. "Pappus Graph. = Incidence Graph of AG(2,3) Minus a Parallel Class" http://www.distanceregular.org/graphs/pappus.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.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. "F018A." http://www.csse.uwa.edu.au/~gordon/foster/F018A.html.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs." http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

Cite this as:

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

Subject classifications