Lower Bound for the Size of Maximal Nontraceable Graphs - Frick, Marietjie; Singleton, Joy (The Electronic Journal of Combinatorics, 2005)
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) ≥ 3n-22 ceil -2 for n 20 and g(n) 3n-22 ceil for n ≥ 54 as well as for n I= {22,23,30,31,38,39,40,41,42,43,46, 47,48,49,50,51}. We show that g(n) = 3n-22 ceil for n ≥ 54 as well as for n I {12,13} and we determine g(n) for n 9.