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 conne ...
, 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 cross ...
. 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 ...
by
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 cross ...
: 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
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 cross ...
. 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 Ha ...
, 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
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 ...
3,
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 ...
4,
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
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* 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 ...
2,
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 for ...
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 gra ...
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 cy ...
. 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 maxima ...
.
Geometry
By
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 grap ...
, 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-con ...
: 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 triangular ...
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 ea ...
. 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.
Exam ...
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-loop ...
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''. A unif ...
.
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 the g ...
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, ge ...
D6, 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 chara ...