Herschel graph: Difference between revisions
overkill source for bipartite; put only salient properties in ibox; add symmetry; swap out goldner harary ref |
|||
| Line 8: | Line 8: | ||
| edges = 18 |
| edges = 18 |
||
| automorphisms = 12 ([[Dihedral group|D]]<sub>6</sub>) |
| automorphisms = 12 ([[Dihedral group|D]]<sub>6</sub>) |
||
| girth = |
| girth = |
||
| diameter = |
| diameter = |
||
| radius = |
| radius = |
||
| chromatic_number = |
| chromatic_number = |
||
| chromatic_index = |
| chromatic_index = |
||
| properties = {{plainlist|1= |
|||
| properties = [[polyhedral graph|Polyhedral]]<br>[[planar graph|Planar]]<br>[[bipartite graph|Bipartite]]<br>[[Perfect graph|Perfect]] |
|||
*[[polyhedral graph|Polyhedral]] |
|||
*[[bipartite graph|Bipartite]] |
|||
*[[Hamiltonian cycle|non-Hamiltonian]] |
|||
}} |
|||
}} |
}} |
||
| Line 21: | Line 25: | ||
The Herschel graph has three vertices of degree four and eight vertices of degree three. Each of the three pairs of degree-four vertices form a cycle of four vertices, in which they alternate with two of the degree-three vertices. Each of the two remaining degree-three vertices is adjacent to a degree-three vertex from each of these three cycles.{{r|clp}} |
The Herschel graph has three vertices of degree four and eight vertices of degree three. Each of the three pairs of degree-four vertices form a cycle of four vertices, in which they alternate with two of the degree-three vertices. Each of the two remaining degree-three vertices is adjacent to a degree-three vertex from each of these three cycles.{{r|clp}} |
||
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 also [[vertex connectivity|3-vertex-connected]]: the removal of any two of its vertices leaves a connected [[Glossary of graph theory#Subgraphs|subgraph]].{{r|mathworld}} It is a [[bipartite graph]]: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture). |
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 also [[vertex connectivity|3-vertex-connected]]: the removal of any two of its vertices leaves a connected [[Glossary of graph theory#Subgraphs|subgraph]].{{r|mathworld}} It is a [[bipartite graph]]: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture).{{r|holton}} |
||
As with any bipartite graph, the Herschel graph is a [[perfect graph]] : the [[chromatic number]] of every [[induced subgraph]] equals the size of the largest [[Glossary of graph theory#Cliques|clique]] of that subgraph. It has also [[chromatic index]] 4, girth 4, radius 3 and diameter 4. |
|||
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.{{r|clp}} |
|||
==Polyhedron== |
==Polyhedron== |
||
| Line 67: | Line 72: | ||
<ref name=herschel>{{citation|last=Herschel|first=A. S.|authorlink=Alexander Stewart Herschel|title=Sir Wm. Hamilton's Icosian Game|url=https://books.google.com/books?id=-w8LAAAAYAAJ&pg=PA305|journal=[[The Quarterly Journal of Pure and Applied Mathematics]]|volume=5|page=305|year=1862}}</ref> |
<ref name=herschel>{{citation|last=Herschel|first=A. S.|authorlink=Alexander Stewart Herschel|title=Sir Wm. Hamilton's Icosian Game|url=https://books.google.com/books?id=-w8LAAAAYAAJ&pg=PA305|journal=[[The Quarterly Journal of Pure and Applied Mathematics]]|volume=5|page=305|year=1862}}</ref> |
||
<ref name=holton>{{citation |
|||
| last = Holton | first = D. A. |
|||
| editor-last = Casse | editor-first = L. R. A. |
|||
| contribution = Cycles in graphs |
|||
| doi = 10.1007/BFb0071507 |
|||
| mr = 731570 |
|||
| pages = 24–48 |
|||
| publisher = Springer | location = Berlin |
|||
| series = Lecture Notes in Mathematics |
|||
| title = Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982 |
|||
| volume = 1036 |
|||
| year = 1983}}</ref> |
|||
<ref name=kirpet>{{citation|last1=Király|first1=Csaba|last2=Péterfalvi|first2=Ferenc|doi=10.1016/j.disc.2012.03.031|issue=15|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|mr=2926099|pages=2262–2271|title=Balanced generic circuits without long paths|volume=312|year=2012|doi-access=free}}</ref> |
<ref name=kirpet>{{citation|last1=Király|first1=Csaba|last2=Péterfalvi|first2=Ferenc|doi=10.1016/j.disc.2012.03.031|issue=15|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|mr=2926099|pages=2262–2271|title=Balanced generic circuits without long paths|volume=312|year=2012|doi-access=free}}</ref> |
||
<ref name=golhar>{{citation|first1=A.|last1=Goldner|first2=F.|last2=Harary|author2-link=Frank Harary|title=Note on a smallest nonhamiltonian maximal planar graph|journal=Bull. Malaysian Math. Soc.|volume=6|issue=1|year=1975|pages=41–42}}; see also the same journal '''6'''(2):33 (1975) and '''8''':104-106 (1977). Reference from [http://www.cs.nmsu.edu/fnh/publ.html listing of Harary's publications].</ref></ref> |
|||
<ref name=golhar>{{mathworld|title=Goldner-Harary Graph|urlname=Goldner-HararyGraph|mode=cs2}}</ref> |
|||
<ref name=mathworld>{{mathworld|title=Herschel Graph|urlname=HerschelGraph|mode=cs2}}</ref> |
<ref name=mathworld>{{mathworld|title=Herschel Graph|urlname=HerschelGraph|mode=cs2}}</ref> |
||
Revision as of 23:32, 24 December 2022
| Herschel graph | |
|---|---|
 The Herschel graph. | |
| Named after | Alexander Stewart Herschel |
| Vertices | 11 |
| Edges | 18 |
| Automorphisms | 12 (D6) |
| 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).
Definition and properties
The Herschel graph has three vertices of degree four and eight vertices of degree three. Each of the three pairs of degree-four vertices form a cycle of four vertices, in which they alternate with two of the degree-three vertices. Each of the two remaining degree-three vertices is adjacent to a degree-three vertex from each of these three cycles.[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 also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph.[2] It is a bipartite graph: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture).[3]
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
The Herschel graph is planar and 3-vertex-connected, so it follows by Steinitz's theorem that it is a polyhedral graph: there exists a convex polyhedron (an enneahedron) having the Herschel graph as its skeleton.[4] This polyhedron has nine quadrilaterals for faces, which can be chosen to form three rhombi and six kites.[1]
Its dual polyhedron is a rectified triangular prism, formed as the convex hull of the midpoints of the edges of a triangular prism. 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 number are also on adjacent faces. Because polyhedral face numberings of this type are used as "spindown life counters" in the game Magic: The Gathering, Constantinides & Constantinides (2018) name the canonical polyhedron realization of this dual polyhedron as "the Lich's nemesis".[5]
Hamiltonicity
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. It is the smallest non-Hamiltonian polyhedral graph, whether the size of the graph is measured in terms of its number of vertices, edges, or faces.[6] There exist other polyhedral graphs with 11 vertices and no Hamiltonian cycles (notably the Goldner–Harary graph)[7] but none with fewer edges.[4]
All but three of the vertices of the Herschel graph have degree three. Tait's conjecture[8] states that a polyhedral graph in which every vertex has degree three must be Hamiltonian, but this was disproved when W. T. Tutte provided a counterexample, the much larger Tutte 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 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, meaning that for every partition of the vertices into two subsets of at least two vertices, there are at least six edges crossing the partition.[13]
History
The Herschel graph is named after British astronomer Alexander Stewart Herschel, who wrote an early paper concerning William Rowan Hamilton's icosian game: the Herschel graph describes the smallest convex polyhedron for which this game has no solution. However, 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] However, the graph itself was described earlier, for instance by H. S. M. Coxeter.[4]
References
- ^ a b c d Lawson-Perfect, Christian (13 October 2013), "An enneahedron for Herschel", The Aperiodical, retrieved 7 December 2016
- ^ Weisstein, Eric W., "Herschel Graph", MathWorld
- ^ 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
- ^ a b c Coxeter, H. S. M. (1973), Regular Polytopes, Dover, p. 8
- ^ 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
- ^ 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.
- ^ 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.
- ^ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46; reprinted in Scientific Papers, vol. II, pp. 85–98
- ^ 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
- ^ Samal, Robert (11 June 2007), Barnette's conjecture, the Open Problem Garden, retrieved 24 Feb 2011
- ^ 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
- ^ 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.
- ^ 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
- ^ Herschel, A. S. (1862), "Sir Wm. Hamilton's Icosian Game", The Quarterly Journal of Pure and Applied Mathematics, 5: 305
- ^ Bondy, J. A.; Murty, U. S. R. (1976), Graph Theory With Applications, North Holland, p. 53, MR 0411988
External links
