Herschel graph

Last updated

Herschel graph
Herschel graph LS.svg
The Herschel graph.
Named after Alexander Stewart Herschel
Vertices 11
Edges 18
Automorphisms 12 (D 6)
Properties
Table of graphs and parameters

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 Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs (but not of this graph).

Contents

Definition and properties

The Herschel graph has three vertices of degree four (the three blue vertices aligned vertically in the center of the illustration) and eight vertices of degree three. Each two distinct degree-four vertices share two degree-three neighbors, forming a four-vertex cycle with these shared neighbors. There are three of these cycles, passing through six of the eight degree-three vertices (red in the illustration). Two more degree-three vertices (blue) do not participate in these four-vertex cycles; instead, each is adjacent to three of the six red vertices. [1]

The Herschel graph is a polyhedral graph; this means that it is a planar graph, one that can be drawn in the plane with none of its edges crossing, and that it is 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph. [1] It is a bipartite graph: when it is colored with five blue and six red vertices, as illustrated, each edge has one red endpoint and one blue endpoint. [2]

It has order-6 dihedral symmetry, for a total of 12 members of its automorphism group. The degree-four vertices can be permuted arbitrarily, giving six permutations, and in addition, for each permutation of the degree-four vertices, there is a symmetry that keeps these vertices fixed and exchanges pairs of degree-three vertices. [1]

Polyhedron

Herschel enneahedron animated.gif
The Herschel graph as a polyhedron
Rectified triangular prism.png
The dual polyhedron, a rectified triangular prism

By Steinitz's theorem, every graph that is planar and 3-vertex-connected has a convex polyhedron with the graph as its skeleton. [3] Because the Herschel graph has these properties, [1] it can be represented in this way by a convex polyhedron, an enneahedron having polyhedron has nine quadrilaterals as its faces. [4] This can be chosen so that each graph automorphism corresponds to a symmetry of the polyhedron, in which case three of the faces will be rhombi or squares, and the other six will be kites. [1]

The dual polyhedron is a rectified triangular prism, which can be formed as the convex hull of the midpoints of the edges of a triangular prism. When constructed in this way, it has three square faces on the same planes as the square faces of the prism, two equilateral triangle faces on the planes of the triangular ends of the prism, and six more isosceles triangle faces. This polyhedron has the property that its faces cannot be numbered in such a way that consecutive numbers appear on adjacent faces, and such that the first and last numbers are also on adjacent faces, because such a numbering would necessarily correspond to a Hamiltonian cycle in the Herschel graph. Polyhedral face numberings of this type are used as "spindown life counters" in the game Magic: The Gathering , to track player lives, by turning the polyhedron to an adjacent face whenever a life is lost. A card in the game, the Lich, allows players to return from a nearly-lost state with a single life to their initial number of lives. Because the dual polyhedron for the Herschel graph cannot be numbered in such a way that this step connects adjacent faces, Constantinides & Constantinides (2018) name the canonical polyhedron realization of this dual polyhedron as "the Lich's nemesis". [5]

Hamiltonicity

A Hamiltonian path (but not cycle) in the Herschel graph Herschel Hamiltonian path.svg
A Hamiltonian path (but not cycle) in the Herschel graph

As a bipartite graph that has an odd number of vertices, the Herschel graph does not contain a Hamiltonian cycle (a cycle of edges that passes through each vertex exactly once). For, in any bipartite graph, any cycle must alternate between the vertices on either side of the bipartition, and therefore must contain equal numbers of both types of vertex and must have an even length. Thus, a cycle passing once through each of the eleven vertices cannot exist in the Herschel graph. A graph is called Hamiltonian whenever it contains a Hamiltonian cycle, so the Herschel graph is not Hamiltonian. It has the smallest number of vertices, the smallest number of edges, and the smallest number of faces of any non-Hamiltonian polyhedral graph. [6] There exist other polyhedral graphs with 11 vertices and no Hamiltonian cycles (notably the Goldner–Harary graph) [7] but none with fewer edges. [6]

All but three of the vertices of the Herschel graph have degree three. A graph is called cubic or 3-regular when all of its vertices have degree three. P. G. Tait conjectured [8] that a polyhedral 3-regular graph must be Hamiltonian; this was disproved when W. T. Tutte provided a counterexample, the Tutte graph, which is much larger than the Herschel graph. [9] A refinement of Tait's conjecture, Barnette's conjecture that every bipartite 3-regular polyhedral graph is Hamiltonian, remains open. [10]

Every maximal planar graph that does not have a Hamiltonian cycle has a Herschel graph as a minor. The Herschel graph is conjectured to be one of three minor-minimal non-Hamiltonian 3-vertex-connected graphs. The other two are the complete bipartite graph and a graph formed by splitting both the Herschel graph and into two symmetric halves by three-vertex separators and then combining one half from each graph. [11]

The medial graph of the Herschel graph is a 4-regular planar graph with no Hamiltonian decomposition. The shaded regions correspond to the vertices of the underlying Herschel graph. Medial Herschel graph.svg
The medial graph of the Herschel graph is a 4-regular planar graph with no Hamiltonian decomposition. The shaded regions correspond to the vertices of the underlying Herschel graph.

The Herschel graph also provides an example of a polyhedral graph for which the medial graph has no Hamiltonian decomposition into two edge-disjoint Hamiltonian cycles. The medial graph of the Herschel graph is a 4-regular graph with 18 vertices, one for each edge of the Herschel graph; two vertices are adjacent in the medial graph whenever the corresponding edges of the Herschel graph are consecutive on one of its faces. [12] It is 4-vertex-connected and essentially 6-edge-connected. Here, a graph is -vertex-connected or -edge-connected if the removal of fewer than vertices or edges (respectively) cannot disconnected it. Planar graphs cannot be 6-edge-connected, because they always have a vertex of degree at most five, and removing the neighboring edges disconnects the graph. The "essentially 6-edge-connected" terminology means that this trivial way of disconnecting the graph is ignored, and it is impossible to disconnect the graph into two subgraphs that each have at least two vertices by removing five or fewer edges. [13]

History

The Herschel graph is named after Alexander Stewart Herschel, a British astronomer, who wrote an early paper concerning William Rowan Hamilton's icosian game. This is a puzzle involving finding Hamiltonian cycles on a polyhedron, usually the regular dodecahedron. The Herschel graph describes the smallest convex polyhedron that can be used in place of the dodecahedron to give a game that has no solution. Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and regular icosahedron; it did not describe the Herschel graph. [14] The name "the Herschel graph" makes an early appearance in a graph theory textbook by John Adrian Bondy and U. S. R. Murty, published in 1976. [15] The graph itself was described earlier, for instance by H. S. M. Coxeter. [4]

Related Research Articles

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait (1884) and disproved by W. T. Tutte (1946), who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.

<span class="mw-page-title-main">Complete graph</span> Graph in which every two vertices are adjacent

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

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. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Grinberg's theorem</span> On Hamiltonian cycles in planar graphs

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

<span class="mw-page-title-main">Hamiltonian decomposition</span>

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

<span class="mw-page-title-main">Tutte graph</span>

In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.

<span class="mw-page-title-main">Polyhedral graph</span> Graph made from vertices and edges of a convex polyhedron

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-connected, planar graphs.

<span class="mw-page-title-main">Goldner–Harary graph</span> Undirected graph with 11 nodes and 27 edges

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. The same graph had already been given as an example of a non-Hamiltonian simplicial polyhedron by Branko Grünbaum in 1967.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

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

<span class="mw-page-title-main">Enneahedron</span> Polyhedron with 9 faces

In geometry, an enneahedron is a polyhedron with nine faces. There are 2606 types of convex enneahedron, each having a different pattern of vertex, edge, and face connections. None of them are regular.

<span class="mw-page-title-main">Barnette–Bosák–Lederberg graph</span> Non-Hamiltonian simple polyhedron

In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic polyhedral graph with no Hamiltonian cycle, the smallest such graph possible. It was discovered in the mid-1960s by Joshua Lederberg, David Barnette, and Juraj Bosák, after whom it is named. It has 38 vertices and 69 edges.

References

  1. 1 2 3 4 5 Lawson-Perfect, Christian (13 October 2013), "An enneahedron for Herschel", The Aperiodical, retrieved 7 December 2016
  2. ↑ Holton, D. A. (1983), "Cycles in graphs", in Casse, L. R. A. (ed.), Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982, Lecture Notes in Mathematics, vol. 1036, Berlin: Springer, pp. 24–48, doi:10.1007/BFb0071507, MR   0731570
  3. ↑ Grünbaum, Branko (2003), "13.1 Steinitz's theorem", Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, pp. 235–244, ISBN   0-387-40409-0
  4. 1 2 Coxeter, H. S. M. (1948), Regular Polytopes , London: Methuen, p. 8
  5. ↑ Constantinides, Anthony F.; Constantinides, George A. (October 2018), "Spindown Polyhedra", The Mathematical Gazette, 102 (555): 447–453, doi:10.1017/mag.2018.111, S2CID   233357977
  6. 1 2 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. ↑ 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.
  8. ↑ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine , 5th Series, 17: 30–46; see paragraph (16), pp. 41–42. Reprinted in Scientific Papers, vol. II, pp. 85–98
  9. ↑ Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98
  10. ↑ Šámal, Robert (11 June 2007), Barnette's conjecture, the Open Problem Garden, retrieved 24 Feb 2011
  11. ↑ Ding, Guoli; Marshall, Emily (2018), "Minimal -connected non-Hamiltonian graphs", Graphs and Combinatorics, 34 (2): 289–312, doi:10.1007/s00373-018-1874-z, MR   3774453, S2CID   253891751
  12. ↑ Bondy, J. A.; Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae , 22 (1): 42–45, doi:10.1007/BF02190157, S2CID   120729891 .
  13. ↑ Király, Csaba; Péterfalvi, Ferenc (2012), "Balanced generic circuits without long paths", Discrete Mathematics , 312 (15): 2262–2271, doi: 10.1016/j.disc.2012.03.031 , MR   2926099
  14. ↑ Herschel, A. S. (1862), "Sir Wm. Hamilton's Icosian Game", The Quarterly Journal of Pure and Applied Mathematics , 5: 305
  15. ↑ Bondy, J. A.; Murty, U. S. R. (1976), Graph Theory With Applications, North Holland, p. 53, MR   0411988
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.