Goldner–Harary graph

From HandWiki
Short description: Undirected graph with 11 nodes and 27 edges
Goldner–Harary graph
File:240px
Named afterA. Goldner,
Frank Harary
Vertices11
Edges27
Radius2
Diameter2
Girth3
Automorphisms12 (D6)
Chromatic number4
Chromatic index8
PropertiesPolyhedral
Planar
Chordal
Perfect
Treewidth 3
Table of graphs and parameters

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 Anita M. 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 Grünbaum in 1967.[4]

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.[5] 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.[5] 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.[6]

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.[7] 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.[8] As a planar 3-tree, it forms an example of an Apollonian network.[9]

An arc diagram of the Goldner–Harary graph. This graph has no Hamiltonian cycle, but can be made Hamiltonian by subdividing the edge crossed by the red dashed line segment and adding two edges along this segment.

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.[10] Nonetheless, it was subsequently shown that all planar graphs have book thickness at most four.[11]

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)2x2(x+2)3(x2−3)(x2−4x−9).

Polyhedron

Geometric realization of the Goldner–Harary graph
Realization of the Goldner–Harary graph as a convex 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.[12] 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.[4][13] 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

  1. ↑ Goldner, A. (1975), "Note on a smallest nonhamiltonian maximal planar graph", Bulletin Malaysian Mathematical Sciences Society 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.
  2. ↑ 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 .
  3. ↑ Read, R. C.; Wilson, R. J. (1998), An Atlas of Graphs, Oxford, England: Oxford University Press, p. 285 .
  4. ↑ 4.0 4.1 Convex Polytopes, Wiley Interscience, 1967, p. 357 . Same page, 2nd ed., Graduate Texts in Mathematics 221, Springer-Verlag, 2003, ISBN 978-0-387-40409-7.
  5. ↑ 5.0 5.1 Tonyl, A. Robina; Tharani, A. Punitha (August 2018), "Triple Connected Line Domination Number for Some Standard and Special Graphs", International Journal of Advanced Scientific Research and Management 3 (8), ISSN 2455-6378 
  6. ↑ Barnette, David; Jucovič, Ernest (1970), "Hamiltonian circuits on 3-polytopes", Journal of Combinatorial Theory 9 (1): 54–59, doi:10.1016/S0021-9800(70)80054-0 .
  7. ↑ Proskurowski, Andrzej (1981), "Recursive graphs, recursive labelings and shortest paths", SIAM Journal on Computing 10 (2): 391–397, doi:10.1137/0210028 
  8. ↑ Pegden, Wesley (2012), "The lefthanded local lemma characterizes chordal dependency graphs", Random Structures & Algorithms (John Wiley & Sons) 41 (4): 546–556, doi:10.1002/rsa.20439 .
  9. ↑ Knill, Oliver (June 17, 2018), "Combinatorial manifolds are Hamiltonian", arXiv:1806.06436 [cs.DM].
  10. ↑ Bernhart, Frank R. (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.
  11. ↑ "Four pages are necessary and sufficient for planar graphs", Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing - STOC '86, 1986, pp. 104–108, doi:10.1145/12130.12141, ISBN 0-89791-193-8 .
  12. ↑ Yadav, Sanlosh Kumar (2023), Advanced Graph Theory, Springer, p. 100, ISBN 978-3-031-22562-8, https://books.google.com/books?id=wM7FEAAAQBAJ&pg=PA100 
  13. ↑ Ewald, Günter (1973), "Hamiltonian circuits in simplicial complexes", Geometriae Dedicata 2 (1): 115–125, doi:10.1007/BF00149287 .




Retrieved from "https://handwiki.org/wiki/index.php?title=Goldner–Harary_graph&oldid=4231174"