On the extremal number of edges in hamiltonian connected graphs

Tung-Yang Ho, Cheng-Kuan Lin, Jiann-Mean Tan, D. Frank Hsu, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.
Original languageEnglish
Pages (from-to)26-29
Number of pages4
JournalApplied Mathematics Letters
Issue number1
StatePublished - Jan 2010


  • Hamiltonian connected
  • Edge-fault tolerant hamiltonian connected

Fingerprint Dive into the research topics of 'On the extremal number of edges in hamiltonian connected graphs'. Together they form a unique fingerprint.

Cite this