Opuscula Math. 29, no. 1 (2009), 89-92

http://dx.doi.org/10.7494/OpMath.2009.29.1.89

Opuscula Mathematica

# 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.

Mathematics Subject Classification: 05C35, 05C38.

- Adam Paweł Wojda
- AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland

- Received: 2008-06-27.
- Accepted: 2008-11-30.