Wagner graph | |
---|---|
The Wagner graph
|
|
Named after | Klaus Wagner |
Vertices | 8 |
Edges | 12 |
Radius | 2 |
Diameter | 2 |
Girth | 4 |
Automorphisms | 16 (D8) |
Chromatic number | 3 |
Chromatic index | 3 |
Genus | 1 |
Properties |
Cubic Hamiltonian Triangle-free Vertex-transitive Toroidal Apex |
Notation | M8 |
In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.
As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, making it an apex graph. It can be embedded without crossings on a torus or projective plane, so it is also a toroidal graph. It has girth 4, diameter 2, radius 2, chromatic number 3, chromatic index 3 and is both 3-vertex-connected and 3-edge-connected.
The Wagner graph has 392 spanning trees; it and the complete graph K3,3 have the most spanning trees among all cubic graphs with the same number of vertices.
The Wagner graph is a vertex-transitive graph but is not edge-transitive. Its full automorphism group is isomorphic to the dihedral group D8 of order 16, the group of symmetries of an octagon, including both rotations and reflections.
The characteristic polynomial of the Wagner graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.