On hypohamiltonian and almost hypohamiltonian graphs. (English) Zbl 1312.05076

Zamfirescu, Carol T.

J. Graph Theory 79, No. 1, 63-81 (2015).

Summary: A graph \(G\) is almost hypohamiltonian if \(G\) is non-Hamiltonian, there exists a vertex \(w\) such that \(G-v\) is non-Hamiltonian, and for any vertex \(v\neq w\) the graph \(G-v\) is Hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4-connected almost hypohamiltonian graph, while Thomassen’s question whether 4-connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order \(n\) for every \(n\geq 74\). During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.

MSC:

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

Keywords:

Grinberg’s criterion; hypohamiltonian graph; planar graph

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 pp #P85– (2011) · Zbl 1217.05065
[3]	Bondy, Variations on the Hamiltonian Theme, Canad Math Bull 15 pp 57– (1972) · Zbl 0238.05115
[4]	Chvátal, Flip-flops in hypohamiltonian graphs, Canad Math Bull 16 pp 33– (1973) · Zbl 0253.05142
[5]	Chvátal, STAN-CS-72-292 (1972)
[6]	Collier, New flip-flop constructions for hypohamiltonian graphs, Discrete Math 18 pp 265– (1977) · Zbl 0367.05046
[7]	Collier, Systematic searches for hypohamiltonian graphs, Networks 8 pp 193– (1978) · Zbl 0384.05046
[8]	Gaudin, Solution de problème no, 29, Rev Franç Rech Opérat 8 pp 214– (1964)
[9]	Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook 4 pp 51– (1968) · Zbl 0185.27901
[10]	Grötschel, On the monotone symmetric travelling salesman problem: hypohamiltonian/hypotraceable graphs and facets, Math Oper Res 5 pp 285– (1980) · Zbl 0442.90070
[11]	Grünbaum, Vertices missed by longest paths or circuits, J Combin Theory, Ser A 17 pp 31– (1974) · Zbl 0259.05120
[12]	Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math Ann 243 pp 213– (1979) · Zbl 0396.05032
[13]	Häggkvist, Problem 443. Special case of the Fulkerson Conjecture. In: ’Research problems from the 5th Slovenian Conference’, Bled, 2003 (B. Mohar, R. J. Nowakowski, and D. B. West, Eds.). Discrete Math 307 pp 650– (2007)
[14]	Holton, The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J Combin Theory, Ser B 45 pp 315– (1988) · Zbl 0607.05051
[15]	Holton, The Petersen Graph, Chapter 7: Hypohamiltonian graphs (1993) · Zbl 0781.05001
[16]	Horton, A Hypotraceable Graph. Research Report CORR 73-4 (1973)
[17]	M. Jooyandeh B. D. McKay P. R. J. Östergård V. H. Pettersson C. T. Zamfirescu Planar hypohamiltonian graphs on 40 vertices
[18]	Kapoor, On detours in graphs, Canad Math Bull 11 pp 195– (1968) · Zbl 0167.22002
[19]	Máčajová, Infinitely many hypohamiltonian cubic graphs of girth 7, Graphs Combin 27 pp 231– (2011) · Zbl 1235.05085
[20]	Park, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoret Comput Sci 377 pp 170– (2007) · Zbl 1115.68116
[21]	Sousselier, Problème no. 29: Le cercle des irascibles, Rev Franç Rech Opérat 7 pp 405– (1963)
[22]	Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math 9 pp 91– (1974) · Zbl 0278.05110
[23]	Thomassen, On hypohamiltonian graphs, Discrete Math 10 pp 383– (1974) · Zbl 0286.05122
[24]	Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math 14 pp 377– (1976) · Zbl 0322.05130
[25]	Thomassen, Lecture Notes in Mathematics 642 pp 557– (1978)
[26]	Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Combin Theory, Ser B 30 pp 36– (1981) · Zbl 0388.05033
[27]	Tutte, On hamiltonian circuits, J London Math Soc 21 pp 98– (1946) · Zbl 0061.41306
[28]	Tutte, A theorem on planar graphs, Trans Amer Math Soc 82 pp 99– (1956) · Zbl 0070.18403
[29]	West, Introduction to Graph Theory, 2nd edn (2001)
[30]	Wiener, On planar hypohamiltonian graphs, J Graph Theory 67 pp 55– (2011) · Zbl 1223.05168
[31]	Zamfirescu, Hypohamiltonian graphs and their crossing number, Electron J Combin 19 pp #P12– (2012) · Zbl 1266.05079
[32]	Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory 55 pp 338– (2007) · Zbl 1120.05054