Retrieve PDF document
(201109_09.pdf) | Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] |
¡@
TUNG-YANG HO+, CHENG-KUAN
LIN1, JIMMY J. M. TAN1, D. FRANK HSU2 AND
LIH-HSING HSU3
+Department
of Information Management
Ta Hwa Institute of Technology
Hsinchu, 307 Taiwan
E-mail: hoho@thit.edu.tw
1Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan
2Department of Computer and Information Science
Fordham University
New York, NY 10023, U.S.A.
3Department 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.