The Goldner–Harary graph is a planar graph: it can be drawn in the plane with none of its edges crossing. When drawn on a plane, all its faces are triangular, making it a maximal planar graph. As with every maximal planar graph, it is also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph.
The Goldner–Harary graph is also non-Hamiltonian. The smallest possible number of vertices for a non-Hamiltonian polyhedral graph is 11. Therefore, the Goldner–Harary graph is a minimal example of graphs of this type. However, the Herschel graph, another non-Hamiltonian polyhedron with 11 vertices, has fewer edges.
As a non-Hamiltonian maximal planar graph, the Goldner–Harary graph provides an example of a planar graph with book thickness greater than two.[5] Based on the existence of such examples, Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large, but it was subsequently shown that all planar graphs have book thickness at most four.[6]
By Steinitz's theorem, the Goldner–Harary graph is a polyhedral graph: it is planar and 3-connected, so there exists a convex polyhedron having the Goldner–Harary graph as its skeleton.
Realization of the Goldner–Harary graph as the deltahedron obtained by attaching regular tetrahedra to the six faces of a triangular dipyramid.
Geometrically, a polyhedron representing the Goldner–Harary graph may be formed by gluing a tetrahedron onto each face of a triangular dipyramid, similarly to the way a triakis octahedron is formed by gluing a tetrahedron onto each face of an octahedron. That is, it is the Kleetope of the triangular dipyramid.[4][7] The dual graph of the Goldner–Harary graph is represented geometrically by the truncation of the triangular prism.
Algebraic properties
The automorphism group of the Goldner–Harary graph is of order 12 and is isomorphic to the dihedral group D6, the group of symmetries of a regular hexagon, including both rotations and reflections.
^Goldner, A.; Harary, F. (1975), "Note on a smallest nonhamiltonian maximal planar graph", Bull. Malaysian Math. Soc., 6 (1): 41–42. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference from listing of Harary's publications.
^Dillencourt, M. B. (1996), "Polyhedra of small orders and their Hamiltonian properties", Journal of Combinatorial Theory, Series B, 66: 87–122, doi:10.1006/jctb.1996.0008.
^Read, R. C.; Wilson, R. J. (1998), An Atlas of Graphs, Oxford, England: Oxford University Press, p. 285.
^Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2. See in particular Figure 9.
^Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proc. 18th ACM Symp. Theory of Computing (STOC), pp. 104–108, doi:10.1145/12130.12141, S2CID 5359519.
Wikimedia Commons has media related to Goldner–Harary graphs.
January 07, 2023
goldner, harary, graph, mathematical, field, graph, theory, simple, undirected, graph, with, vertices, edges, named, after, goldner, frank, harary, proved, 1975, that, smallest, hamiltonian, maximal, planar, graph, same, graph, already, been, given, example, h. In the mathematical field of graph theory the Goldner Harary graph is a simple undirected graph with 11 vertices and 27 edges It is named after A Goldner and Frank Harary who proved in 1975 that it was the smallest non Hamiltonian maximal planar graph 1 2 3 The same graph had already been given as an example of a non Hamiltonian simplicial polyhedron by Branko Grunbaum in 1967 4 Goldner Harary graphNamed afterA Goldner Frank HararyVertices11Edges27Radius2Diameter2Girth3Automorphisms12 D6 Chromatic number4Chromatic index8PropertiesPolyhedralPlanarChordalPerfectTreewidth 3Table of graphs and parameters Contents 1 Properties 2 Geometry 3 Algebraic properties 4 References 5 External linksProperties EditThe Goldner Harary graph is a planar graph it can be drawn in the plane with none of its edges crossing When drawn on a plane all its faces are triangular making it a maximal planar graph As with every maximal planar graph it is also 3 vertex connected the removal of any two of its vertices leaves a connected subgraph The Goldner Harary graph is also non Hamiltonian The smallest possible number of vertices for a non Hamiltonian polyhedral graph is 11 Therefore the Goldner Harary graph is a minimal example of graphs of this type However the Herschel graph another non Hamiltonian polyhedron with 11 vertices has fewer edges As a non Hamiltonian maximal planar graph the Goldner Harary graph provides an example of a planar graph with book thickness greater than two 5 Based on the existence of such examples Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large but it was subsequently shown that all planar graphs have book thickness at most four 6 It has book thickness 3 chromatic number 4 chromatic index 8 girth 3 radius 2 diameter 2 and is a 3 edge connected graph It is also a 3 tree and therefore it has treewidth 3 Like any k tree it is a chordal graph As a planar 3 tree it forms an example of an Apollonian network Geometry EditBy Steinitz s theorem the Goldner Harary graph is a polyhedral graph it is planar and 3 connected so there exists a convex polyhedron having the Goldner Harary graph as its skeleton Realization of the Goldner Harary graph as the deltahedron obtained by attaching regular tetrahedra to the six faces of a triangular dipyramid Geometrically a polyhedron representing the Goldner Harary graph may be formed by gluing a tetrahedron onto each face of a triangular dipyramid similarly to the way a triakis octahedron is formed by gluing a tetrahedron onto each face of an octahedron That is it is the Kleetope of the triangular dipyramid 4 7 The dual graph of the Goldner Harary graph is represented geometrically by the truncation of the triangular prism Algebraic properties EditThe automorphism group of the Goldner Harary graph is of order 12 and is isomorphic to the dihedral group D6 the group of symmetries of a regular hexagon including both rotations and reflections The characteristic polynomial of the Goldner Harary graph is x 1 2 x 2 x 2 3 x 2 3 x 2 4 x 9 displaystyle x 1 2 x 2 x 2 3 x 2 3 x 2 4x 9 References Edit Goldner A Harary F 1975 Note on a smallest nonhamiltonian maximal planar graph Bull Malaysian Math Soc 6 1 41 42 See also the same journal 6 2 33 1975 and 8 104 106 1977 Reference from listing of Harary s publications Dillencourt M B 1996 Polyhedra of small orders and their Hamiltonian properties Journal of Combinatorial Theory Series B 66 87 122 doi 10 1006 jctb 1996 0008 Read R C Wilson R J 1998 An Atlas of Graphs Oxford England Oxford University Press p 285 a b Grunbaum Branko 1967 Convex Polytopes Wiley Interscience p 357 Same page 2nd ed Graduate Texts in Mathematics 221 Springer Verlag 2003 ISBN 978 0 387 40409 7 Bernhart Frank R Kainen Paul C 1979 The book thickness of a graph Journal of Combinatorial Theory Series B 27 3 320 331 doi 10 1016 0095 8956 79 90021 2 See in particular Figure 9 Yannakakis Mihalis 1986 Four pages are necessary and sufficient for planar graphs Proc 18th ACM Symp Theory of Computing STOC pp 104 108 doi 10 1145 12130 12141 S2CID 5359519 Ewald Gunter 1973 Hamiltonian circuits in simplicial complexes Geometriae Dedicata 2 1 115 125 doi 10 1007 BF00149287 S2CID 122755203 External links EditWeisstein Eric W Goldner Harary graph MathWorld Wikimedia Commons has media related to Goldner Harary graphs Retrieved from https en wikipedia org w index php title Goldner Harary graph amp oldid 1097363062, wikipedia, wiki, book, books, library,
