Polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. According to Steinitz's theorem, the polyhedral graphs may also be characterized in purely graph-theoretic terms, as the 3-vertex-connected planar graphs.[1][2]
Tait conjectured that every cubic polyhedral graph (that is, a polyhedral graph in which each vertex is incident to exactly three edges) has a Hamiltonian cycle, but this conjecture was disproved by a counterexample of W. T. Tutte, the polyhedral but non-Hamiltonian Tutte graph. More strongly, there exists a constant α < 1 (the shortness exponent) and an infinite family of polyhedral graphs such that the length of the longest simple path of an n-vertex graph in the family is O(nα).[3][4] If one relaxes the requirement that the graph be cubic, there are much smaller non-Hamiltonian graphs; the one with the fewest vertices and edges is the 11-vertex and 18-edge Herschel graph,[5] and there also exists an 11-vertex non-Hamiltonian graph in which all faces are triangles, the Goldner–Harary graph.[6]
Duijvestijn provides a count of the polyhedral graphs with up to 26 edges;[7] The number of these graphs with 6, 7, 8, ... edges is
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sequence A002840 in the OEIS).
One may also enumerate the polyhedral graphs by their numbers of vertices: for graphs with 4, 5, 6, ... vertices, the number of polyhedral graphs is
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (sequence A000944 in the OEIS).
References
- ^ Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 038794365X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.
- ^ Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Gunter M. Ziegler, 2003, ISBN 0387404090, ISBN 978-0387404097, 466pp.
- ^ Weisstein, Eric W. "Shortness Exponent". MathWorld..
- ^ Grünbaum, Branko; Motzkin, T. S. (1962), "Longest simple paths in polyhedral graphs", Journal of the London Mathematical Society, s1-37 (1): 152–160, doi:10.1112/jlms/s1-37.1.152.
- ^ Weisstein, Eric W. "Herschel Graph". MathWorld..
- ^ Weisstein, Eric W. "Goldner-Harary Graph". MathWorld..
- ^ Duijvestijn, A. J. W. (1996), "The number of polyhedral (3-connected planar) graphs", Mathematics of Computation, 65: 1289–1293, doi:10.1090/S0025-5718-96-00749-1.