### Further results on Maximal Nontraceable graphs of smallest size

*Joy Elizabeth Singleton, Alewyn Petrus Burger*

#### Abstract

Let g(n) denote the minimum number of edges of a maximal
nontraceable (MNT) graph of order n. In 2005 Frick and
Singleton (Lower bound for the size of maximal nontraceable graphs,

*Electronic Journal of Combinatorics*, 12(1) R32, 2005) proved that g(n) = ⌈3n-22 ⌉ for n ≥54 as well as for n ∈I, where I= {12,13,22,23,30,31,38,39, 40,41,42,43,46,47,48,49,50,51} and they determined g(n) for n ≤9. We determine g(n) for 18 of the remaining 26 values of n, showing that g(n) = ⌈ 3n-22 ⌉ for n ≥54 as well as for n ∈I ∪{18,19,20,21,24,25,26,27,28, 29,32,33} and g(n) = ⌈ 3n2 ⌉ for n ∈{ 10, 11, 14, 15, 16, 17}. We give results based on ``analytic'' proofs as well as computer searches.Full Text: PDF PostScript