Planar hypohamiltonian graphs on 40 vertices. (English) Zbl 1356.05029

Jooyandeh, Mohammadreza; McKay, Brendan D.; Östergård, Patric R. J.; Pettersson, Ville H.; Zamfirescu, Carol T.

J. Graph Theory 84, No. 2, 121-133 (2017).

Summary: A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to M. Araya and G. Wiener [Electron. J. Comb. 18, No. 1, Research Paper P85, 11 p. (2011; Zbl 1217.05065)]. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C45	Eulerian and Hamiltonian graphs

Keywords:

graph generation; Grinberg’s theorem; hypo-Hamiltonian graph; hypotraceable graph; planar graph

Citations:

Zbl 1217.05065

Software:

House of Graphs

References:

[1]	Aldred, Small hypohamiltonian graphs, J Combin Math Combin Comput 23 pp 143– (1997) · Zbl 0880.05061
[2]	Araya, On cubic planar hypohamiltonian and hypotraceable graphs, Electron J Combin 18 (1) pp #P85– (2011) · Zbl 1217.05065
[3]	Brinkmann, House of graphs: A database of interesting graphs, Discrete Appl Math 161 pp 311– (2013) · Zbl 1292.05254
[4]	Brinkmann, Construction of planar triangulations with minimum degree 5, Discrete Math 301 pp 147– (2005) · Zbl 1078.05022
[5]	Chvátal, Flip-flops in hypohamiltonian graphs, Can Math Bull 16 pp 33– (1973) · Zbl 0253.05142
[6]	Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook 4 pp 51– (1968) · Zbl 0185.27901
[7]	Grünbaum, Vertices missed by longest paths or circuits, J Combin Theory Ser A 17 pp 31– (1974) · Zbl 0259.05120
[8]	Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math Ann 243 pp 213– (1979) · Zbl 0396.05032
[9]	M. Jooyandeh Planar hypohamiltonian graphs data http://www.jooyandeh.com/planar_hypo
[10]	Shabbir, Intersecting longest paths and longest cycles: A survey, Electron J Graph Theory Appl 1 pp 56– (2013) · Zbl 1306.05121
[11]	Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math 9 pp 91– (1974) · Zbl 0278.05110
[12]	Thomassen, On hypohamiltonian graphs, Discrete Math 10 pp 383– (1974) · Zbl 0286.05122
[13]	Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math 14 pp 377– (1976) · Zbl 0322.05130
[14]	Thomassen, Hypohamiltonian graphs and digraphs, In: Theory and Applications of Graphs pp 557– (1978) · Zbl 0371.05015
[15]	Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Combin Theory Ser B 30 pp 36– (1981) · Zbl 0388.05033
[16]	West, Introduction to Graph Theory (2001)
[17]	Wiener, On planar hypohamiltonian graphs, J Graph Theory 67 pp 55– (2011) · Zbl 1223.05168
[18]	Zaks, Non-Hamiltonian non-Grinbergian graphs, Discrete Math 17 pp 317– (1977) · Zbl 0357.05052
[19]	Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory 55 pp 338– (2007) · Zbl 1120.05054
[20]	Zamfirescu, A two-connected planar graph without concurrent longest paths, J Combin Theory Ser B 13 pp 116– (1972) · Zbl 0243.05110
[21]	Zamfirescu, On longest paths and circuits in graphs, Math Scand 38 pp 211– (1976) · Zbl 0337.05127