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