| Wiener-Araya graph | |
|---|---|
 | |
| Vertices | 42 |
| Edges | 67 |
| Radius | 5 |
| Diameter | 7 |
| Girth | 4 |
| Automorphisms | 2 |
| Chromatic number | 3 |
| Chromatic index | 4 |
| Properties |
Hypohamiltonian Planar |
| Table of graphs and parameters | |
The WienerâAraya graph is, in graph theory, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It is also planar.
History
Hypohamiltonian graphs were first studied by Sousselier in ProblÚmes plaisants et délectables (1963). [1] In 1967, Lindgren built an infinite sequence of hypohamiltonian graphs. [2] He first cited Gaudin, Herz and Rossi, [3] then Busacker and Saaty [4] as pioneers on this topic.
From the start, the smallest hypohamiltonian graph is known: the Petersen graph. However, the hunt for the smallest planar hypohamiltonian graph continues. This question was first raised by VĂĄclav ChvĂĄtal in 1973. [5] The first candidate answer was provided in 1976 by Carsten Thomassen, who exhibited a 105-vertices construction, the 105-Thomassen graph. [6] In 1979, Hatzel improved this result with a planar hypohamiltonian graph on 57 vertices : the Hatzel graph. [7] This bound was lowered in 2007 by the 48-Zamfirescu graph. [8]
In 2009, a graph built by GĂĄbor Wiener and Makoto Araya became (with its 42 vertices) the smallest planar hypohamiltonian graph known. [9] [10] In their paper, Wiener and Araya conjectured their graph to be optimal arguing that its order ( 42) appears to be the answer to The Ultimate Question of Life, the Universe, and Everything from The Hitchhiker's Guide to the Galaxy, a Douglas Adams novel. However, subsequently, smaller planar hypohamiltonian graphs have been discovered. [11]
References
- ^ Sousselier, R. (1963), ProblĂšme no. 29: Le cercle des irascibles, vol. 7, Rev. Franç. Rech. OpĂ©rationnelle, pp. 405â406
- ^ Lindgren, W. F. (1967), "An infinite class of hypohamiltonian graphs", American Mathematical Monthly, 74 (9): 1087â1089, doi: 10.2307/2313617, JSTOR 2313617, MR 0224501
- ^ Gaudin, T.; Herz, P.; Rossi (1964), "Solution du problĂšme No. 29", Rev. Franç. Rech. OpĂ©rationnelle (in French), 8: 214â218
- ^ Busacker, R. G.; Saaty, T. L. (1965), Finite Graphs and Networks
- ^ ChvĂĄtal, V. (1973), "Flip-flops in hypo-Hamiltonian graphs", Canadian Mathematical Bulletin, 16: 33â41, doi: 10.4153/cmb-1973-008-9, MR 0371722
- ^ Thomassen, Carsten (1976), "Planar and infinite hypohamiltonian and hypotraceable graphs", Discrete Mathematics, 14 (4): 377â389, doi: 10.1016/0012-365x(76)90071-6, MR 0422086
- ^ Hatzel, Wolfgang (1979), "Ein planarer hypohamiltonscher Graph mit 57 Knoten", Mathematische Annalen (in German), 243 (3): 213â216, doi: 10.1007/BF01424541, MR 0548801, S2CID 121794449
- ^ Zamfirescu, Carol T.; Zamfirescu, Tudor I. (2007), "A planar hypohamiltonian graph with 48 vertices", Journal of Graph Theory, 55 (4): 338â342, doi: 10.1002/jgt.20241, MR 2336805, S2CID 260477281
- ^ Wiener, GĂĄbor; Araya, Makoto (April 20, 2009), The ultimate question, arXiv: 0904.3012, Bibcode: 2009arXiv0904.3012W.
- ^ Wiener, GĂĄbor; Araya, Makoto (2011), "On planar hypohamiltonian graphs", Journal of Graph Theory, 67 (1): 55â68, doi: 10.1002/jgt.20513, MR 2809563, S2CID 5340663.
- ^ Jooyandeh, Mohammadreza; McKay, Brendan D.; ĂstergĂ„rd, Patric R. J.; Pettersson, Ville H.; Zamfirescu, Carol T. (2017), "Planar hypohamiltonian graphs on 40 vertices", Journal of Graph Theory, 84 (2): 121â133, arXiv: 1302.2698, doi: 10.1002/jgt.22015, MR 3601121, S2CID 5535167