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.

Full text (pdf)

• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland