On the extremal number of edges in hamiltonian connected graphs

Abstract

Assume that n and delta are positive integers with 3 <= delta < n. Let hc(n, delta) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree delta(G) >= delta to be haimiltonian connected. Any n-vertex graph G with delta(G) >= delta is hamiltonian connected if vertical bar E(G)vertical bar >= hc(n, delta). We prove that hc(n, delta) = C(n - delta + 1, 2) + delta(2) - delta + 1 if delta <= [n+3x(n mod 2)/6] + 1, hc(n, delta) = C(n - [n/2] + 1, 2) + [n/w](2) - [n/2] + 1 if [n+3x(n mod 2)/6] + 1 < delta <= [n/2], and hc(n, delta) = [n delta/2] if delta > [n/2]. (C) 2009 Elsevier Ltd. All rights reserved.