Goldner–Harary graph

Properties

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 non-Hamiltonian, meaning there cannot exist a cycle passing once through each of the eleven vertices. The smallest possible number of vertices for a non-Hamiltonian polyhedral graph is 11. Therefore, the Goldner–Harary graph is a minimal example of this type. However, the Herschel graph, another non-Hamiltonian polyhedron with 11 vertices, has fewer edges.

The Goldner–Harary is 3-tree, constructed from a complete graph on two vertices, repeatedly adding vertices until the graph has exactly three neighbors, which forms a clique. Like any k -tree, it has treewidth 3, and its graph is maximal, meaning it can add no more edges without increasing its treewidth. Both of its maximal cliques and clique separators have the same size, hence the graph is chordal. As a planar 3-tree, it forms an example of an Apollonian network.

As a non-Hamiltonian maximal planar graph, the Goldner–Harary graph provides an example of a planar graph with book thickness greater than two. Equivalently, it does not have a planar arc diagram with all vertices on a line and all edges drawn as curves that stay on a single side of the line. Based on the existence of such examples, Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large. Nonetheless, it was subsequently shown that all planar graphs have book thickness at most four.

It has book thickness 3, chromatic number 4, chromatic index 8, girth 3, radius 2, diameter 2 and is a 3-edge-connected graph.

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.

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).

Polyhedron

By Steinitz's theorem, the Goldner–Harary graph is a polyhedral graph: it is 3-connected planar, so there exists a convex polyhedron having the Goldner–Harary graph as its skeleton. Geometrically, the Goldner–Harary graph represents a simplicial polyhedron, a polyhedron with triangular faces. The polyhedron is constructed by gluing tetrahedra onto each face of a triangular dipyramid, the Kleetope of the triangular dipyramid. If the tetrahedra are regular tetrahedron, meaning their faces are equilateral triangles and all edges are of equal length, the result is a non-convex deltahedron.

The dual graph of the Goldner–Harary graph is represented geometrically by the truncation of the triangular prism.

References

| doi-access = free

| doi-access = free

• {{citation
• {{citation | article-number = 71
• {{citation