@Article{Wojda2009,
author = "Wojda, Adam Paweł",
title = "Extremal traceable graphs with non-traceable edges",
journal = "Opuscula Math.",
year = "2009",
volume = "29",
number = "1",
pages = "89--92",
doi = "http://dx.doi.org/10.7494/OpMath.2009.29.1.89",
url = "http://dx.doi.org/10.7494/OpMath.2009.29.1.89",
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",
issn = "1232-9274"
}