Lower bound for the size of maximal nontraceable graphs

2004/07/16 by Marietjie Frick, Frick, Marietjie, Joy Singleton +1
Mathematics · #05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38

paper · pdf · doi:10.48550/arxiv.math/0407292

10 pages, 3 figures

arxiv created 2004/07/16 · arxiv updated 2009/12/01

Abstract

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)≥\ceil(3n-2)/2-2 for n≥ 20 and g(n)≤\ceil(3n-2)/2 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)=\ceil(3n-2)/2 for n≥ 54 as well as for n∈ I∪12,13 and we determine g(n) for n≤ 9.

Related

• Cubic maximal nontraceable graphs
• The maximum size of a nonhamiltonian graph with given order and connectivity
• The maximum size of a graph with prescribed order, circumference and minimum degree
• The minimal size of a graph with generalized connectivity κ₃ = 2
• The minimal size of graphs with given pendant-tree connectivity