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

@

Journal of Information Science and Engineering, Vol. 27 No. 5, pp. 1659-1665 (September 2011)

On the Extremal Number of Edges in Hamiltonian Graphs*

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

Full Text () 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.