Skip to Main content Skip to Navigation
Journal articles

Further results on maximal nontraceable graphs of smallest size

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990607
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:28:51 PM
Last modification on : Monday, October 19, 2020 - 8:00:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:33:31 PM

File

2136-7732-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990607, version 1

Collections

Citation

Alewyn Petrus Burger, Joy Elizabeth Singleton. Further results on maximal nontraceable graphs of smallest size. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.75--92. ⟨hal-00990607⟩

Share

Metrics

Record views

246

Files downloads

1302