JISE


  [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


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 thath(n, δ) = C(n - δ, 2) + δ2 + 1 if  

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

  Retrieve PDF document (JISE_201105_09.pdf)