No label defined (Q4518404)

The toughness, \(t(G)\), of any graph \(G\) is defined, following \textit{V.~Chvátal} [Tough graphs and Hamiltonian circuits, Discrete Math. 5, 215-228 (1973; Zbl 0256.05122)], by \[ t(G)=\operatorname {min} \left \{ \frac {|S|} {\omega (G-S)} : S\subseteq V(G), \;\omega (G-S)>1\right \} \] where \(\omega (G-S)\) is the number of components of \(G - S\). Toughness \(t(G)\) and connectivity \(\mathcal K(G)\) are related by the inequality \(t(G)\leq \frac 1{2}\mathcal K(G)\). By a theorem of \textit{W.~T. Tutte} [A theorem on planar graphs, Trans. Am. Math. Soc. 82, 99-116 (1956; Zbl 0070.18403)], if \(G\) is planar and 4-connected, then \(G\) is hamiltonian. It follows that if \(G\) is planar, 3-connected and non-hamiltonian, then \(\mathcal K(G)=3\) and \(t(G)\leq \frac 3{2}\). Non-hamiltonian regular planar 3-connected graphs of degrees 3, 4 and 5 and with toughness \(\frac 3{2}\) were constructed by \textit{J. Harant} [Toughness and nonhamiltonicity of polyhedral graphs, Discrete Math. 113, No. 1-3, 249-253 (1993; Zbl 0771.05057)]. In \textit{J. Harant} and \textit{P. J. Owens} [Non-hamiltonian \(5\over 4\)-tough maximal planar graphs, Discrete Math. 147, No. 1-3, 301-305 (1995; Zbl 0838.05043)], non-hamiltonian maximal planar graphs with toughness \(5\over 4\) were constructed and the shortness exponent of the family of such graphs was shown to be less than one. In this paper non-hamiltonian maximal planar graphs with toughness greater than \(3\over 2 - \delta \), were \(\delta \) is an arbitrarily small positive number, are constructed and it is shown that the family of such graphs has a shortness coefficient less than one. It is an open question whether there exist non-hamiltonian maximal planar graphs.