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 \(t_{\max}(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).

Keywords

• traceable graph
• non-traceable edge