Further results on maximal nontraceable graphs of smallest sizeReport as inadecuate




Further results on maximal nontraceable graphs of smallest size - Download this document for free, or read online. Document in PDF available to download.

1 Department of Logistics Stellenbosch 2 UNISA - Department of Mathematical Sciences South Africa

Abstract : Let gn 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, 121 R32, 2005 proved that gn = ⌈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 gn for n ≤9. We determine gn for 18 of the remaining 26 values of n, showing that gn = ⌈ 3n-22 ⌉ for n ≥54 as well as for n ∈I ∪18,19,20,21,24,25,26,27,28, 29,32,33 and gn = ⌈ 3n2 ⌉ for n ∈ 10, 11, 14, 15, 16, 17. We give results based on -analytic- proofs as well as computer searches.





Author: Alewyn Petrus Burger - Joy Elizabeth Singleton -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents