Cubic maximal nontraceable graphs (Q868358): Difference between revisions

The authors determine a lower bound for the number of edges of a 2-connected maximal nontraceable graph and present a construction of an infinite family of maximal nontraceable graphs that realizes this bound. The construction proposed by the authors yields maximal nontraceable graphs of girth 5, 6 and 7. The problem of the existence of maximal nontraceable graphs of girth bigger than 7 remains open.