Lower Bound for the Size of Maximal Nontraceable Graphs

Abstract

Let $g(n)$ denote the minimum number of edges of a maximal nontraceable graph of order $n$. Dudek, Katona and Wojda (2003) showed that $ g(n) \geq \lceil {3n-2\over2} \rceil -2$ for $ n \ge 20$ and $ g(n) \le \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I= \{22,23,30,31,38,39,40,41,42,43,46,$ $47,48,49,50,51\}$. We show that $ g(n) = \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I \cup \{12,13\}$ and we determine $g(n)$ for $n \le 9$.