Extremal traceable graphs with non-traceable edges

Abstract

By $\text{NT}(n)$ we denote the set of graphs of order $n$ which are traceable but have non-traceable edges, i.e. edges which are not contained in any hamiltonian path. The class $\text{NT}(n)$ has been considered by Balińska and co-authors in a paper published in 2003, where it was proved that the maximum size tmax(n) of a graph in $\text{NT}(n)$ is at least $(n^2-5n+14)/2$ (for $n \geq 12$). The authors also found $t_{\max}(n)$ for $5 \leq n \leq 11$. We prove that, for $n \geq 5$, $t_{\max}(n) = max\left\{ {{n-2}\choose{2}}+4, {{n-\lfloor\frac{n-1}{2}\rfloor}\choose{2}}+\lfloor\frac{n-1}{2}\rfloor^2\right\}$ and, moreover, we characterize the extremal graphs (in fact we prove that these graphs are exactly those already described in the paper by Balinska et al.). We also prove that a traceable graph of order $n \geq 5$ may have at most $\lceil\frac{n-3}{2}\rceil \lfloor\frac{n-3}{2}\rfloor$ non traceable edges (this result was conjectured in the mentioned paper by Balinska and co-authors).