On planar hypohamiltonian graphs.(English)Zbl 1223.05168

Summary: We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer $$N$$, such that for every integer $$n\geq N$$ there exists a planar hypohamiltonian/hypotraceable graph on $$n$$ vertices.

MSC:

 05C45 Eulerian and Hamiltonian graphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
Full Text:

References:

 [1] Chvátal, Flip-flops in hypohamiltonian graphs, Can Math Bull 16 pp 33– (1973) · Zbl 0253.05142 [2] Gallai, Theory of Graphs pp 115– (1968) [3] Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook, Izdat Zinatne, Riga 4 pp 51– (1968) · Zbl 0185.27901 [4] Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math Ann 243 pp 213– (1979) · Zbl 0396.05032 [5] Holton, The Petersen Graph (1993) · Zbl 0781.05001 [6] Sousselier, Probleme no. 29 le cercle des irascibles, Rev Franç Rech Operat 7 pp 405– (1963) [7] Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math 9 pp 91– (1974) · Zbl 0278.05110 [8] Thomassen, On hypohamiltonian graphs, Discrete Math 10 pp 383– (1974) · Zbl 0286.05122 [9] Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math 14 pp 377– (1976) · Zbl 0322.05130 [10] Thomassen, Theory and Applications of Graphs pp 557– (1978) [11] Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Comb Theory B 30 pp 36– (1981) · Zbl 0388.05033 [12] Voss, Cycles and Bridges in Graphs (1990) · Zbl 0731.05031 [13] Walther, Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen, J Comb Theory 6 pp 1– (1969) · Zbl 0184.27504 [14] Zamfirescu, A two-connected planar graph without concurrent longest paths, J Comb Theory B 13 pp 116– (1972) · Zbl 0243.05110 [15] Zamfirescu, On longest paths and circuits in graphs, Math Scand 38 pp 211– (1976) · Zbl 0337.05127 [16] Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory 55 pp 338– (2007) · Zbl 1120.05054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.