In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Goldner–Harary graph is a simple

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

with 11 vertices and 27 edges. It is named after A. Goldner and

Frank Harary Frank Harary (March 11, 1921 – January 4, 2005) was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory. Harary was a master of clear exposition and, together with ...

, who proved in 1975 that it was the smallest non-Hamiltonian

maximal planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cr ...

. The same graph had already been given as an example of a non-Hamiltonian

simplicial polyhedron In geometry, a simplicial polytope is a polytope whose facets are all simplices. For example, a ''simplicial polyhedron'' in three dimensions contains only triangular facesPolyhedra, Peter R. Cromwell, 1997. (p.341) and corresponds via Steinitz's ...

Branko Grünbaum Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descent

Properties

The Goldner–Harary graph is a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

: 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

. 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 In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph (the graph of a convex polyhedron), and is the smallest polyhedral graph that does not have a ...

, 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 In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...

greater than two. 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.. It has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

8, girth 3,

radius In classical geometry, a radius ( : radii) of a circle or sphere is any of the line segments from its center to its perimeter, and in more modern usage, it is also their length. The name comes from the latin ''radius'', meaning ray but also the ...

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

2 and is a 3- edge-connected graph. It is also a 3-tree, and therefore it has

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gr ...

3. Like any ''k''-tree, it is a

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

. As a planar 3-tree, it forms an example of an

Apollonian network In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maxim ...

Geometry

Steinitz's theorem In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs ...

, the Goldner–Harary graph is a

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. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-c ...

: it is planar and 3-connected, so there exists a convex polyhedron having the Goldner–Harary graph as its

skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

Geometrically, a polyhedron representing the Goldner–Harary graph may be formed by gluing a tetrahedron onto each face of a

triangular dipyramid In geometry, the triangular bipyramid (or dipyramid) is a type of hexahedron, being the first in the infinite set of face-transitive bipyramids. It is the dual of the triangular prism with 6 isosceles triangle faces. As the name suggests, it ...

, similarly to the way a

triakis octahedron In geometry, a triakis octahedron (or trigonal trisoctahedron or kisoctahedronConway, Symmetries of things, p. 284) is an Archimedean dual solid, or a Catalan solid. Its dual is the truncated cube. It can be seen as an octahedron with triangul ...

is formed by gluing a tetrahedron onto each face of an

octahedron In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at e ...

. That is, it is the

Kleetope In geometry and polyhedral combinatorics, the Kleetope of a polyhedron or higher-dimensional convex polytope is another polyhedron or polytope formed by replacing each facet of with a shallow pyramid. Kleetopes are named after Victor Klee. Ex ...

of the triangular dipyramid.. Same page, 2nd ed., Graduate Texts in Mathematics 221, Springer-Verlag, 2003, .. The

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

of the Goldner–Harary graph is represented geometrically by the

truncation In mathematics and computer science, truncation is limiting the number of digits right of the decimal point. Truncation and floor function Truncation of positive real numbers can be done using the floor function. Given a number x \in \mathbb ...

of the

triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. ...

Algebraic properties

The

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is th ...

of the Goldner–Harary graph is of order 12 and is isomorphic to the

dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ...

D₆, the group of symmetries of a

regular hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A '' regular hexagon'' has ...

, including both rotations and reflections. The

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the Goldner–Harary graph is :

-(x-1)^2 x^2 (x+2)^3 (x^2-3) (x^2-4 x-9)

References

External links

* {{Commons Individual graphs Planar graphs