Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] |

¡@

TUNG-YANG HO^{+}, CHENG-KUAN
LIN^{1}, JIMMY J. M. TAN^{1}, D. FRANK HSU^{2} AND
LIH-HSING HSU^{3}

* ^{+}Department
of Information Management
Ta Hwa Institute of Technology
Hsinchu, 307 Taiwan
E-mail: hoho@thit.edu.tw
^{1}Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan
^{2}Department of Computer and Information Science
Fordham University
New York, NY 10023, U.S.A.
^{3}Department of Computer Science and Information Engineering
Providence University
Taichung, 433 Taiwan *

Assume that *n* and *£_* are positive integers with 2 <= *£_* <
*n*. Let *h*(*n*, *£_*) be the minimum number of edges
required to guarantee an *n*-vertex graph with minimum degree *£_*(*G*)
>= *£_* to be hamiltonian,* i.e*., any *n*-vertex graph
*G* with *£_*(*G*) >= *£_* is hamiltonian if |*E*(*G*)|
>= *h*(*n*, *£_*). We prove that *h*(*n*, *£_*)
= *C*(*n* - *£_*, 2) + *£_*^{2} + 1 if

* Keywords: * complete graph,
cycle, hamiltonian, hamiltonian cycle, edge-fault tolerant hamiltonian

Retrieve PDF document
(**201109_09.pdf**)

Received December 11, 2009; revised April 6, 2010;
accepted April 23, 2010.

Communicated by Ding-Zhu Du.

^{*} This work was supported by the National Science Council of Taiwan,
R.O.C. under Contract No. NSC 98- 2115-M-233-001.

^{+} Corresponding author.