標題: On the Extremal Number of Edges in Hamiltonian Graphs
作者: Ho, Tung-Yang
Lin, Cheng-Kuan
Tan, Jimmy J. M.
Hsu, D. Frank
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: complete graph;cycle;hamiltonian;hamiltonian cycle;edge-fault tolerant hamiltonian
公開日期: 1-九月-2011
摘要: Assume that n and delta are positive integers with 2 <= delta < n. Let h(n, delta) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree delta(G) >= delta be hamiltonian, i.e., any n-vertex graph G with delta(G) >= delta is hamiltonian if vertical bar E(G)vertical bar >= h(n, delta). We move that h(n, delta) = (n - delta, 2) + delta(2) +1 if delta <= left perpendicular n + 1 + x ((n + 1mld 2)/6 right perpendicular, h(n, delta) = C(n - left perpendicular n - 1/2 right perpendicular, 2) + left perpendicular n - 1/2 right perpendicular(2) + 1 if left perpendicular n + 1 + 3 x ((n + 1) mod2)/6 < delta <= left perpendicular n - 1/2 right perpendicular, and h(n, delta, = inverted right perpendicular n delta/2inverted left perpendicular if delta > left perpendicular n - 1/2 right perpendicular.
URI: http://hdl.handle.net/11536/19337
ISSN: 1016-2364
期刊: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 27
Issue: 5
起始頁: 1659
結束頁: 1665
顯示於類別:期刊論文


文件中的檔案:

  1. 000295605300009.pdf