標題: On the extremal number of edges in hamiltonian connected graphs
作者: Ho, Tung-Yang
Lin, Cheng-Kuan
Tan, Jimmy J. M.
Hsu, D. Frank
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian connected;Edge-fault tolerant hamiltonian connected
公開日期: 1-Jan-2010
摘要: Assume that n and delta are positive integers with 3 <= delta < n. Let hc(n, delta) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree delta(G) >= delta to be haimiltonian connected. Any n-vertex graph G with delta(G) >= delta is hamiltonian connected if vertical bar E(G)vertical bar >= hc(n, delta). We prove that hc(n, delta) = C(n - delta + 1, 2) + delta(2) - delta + 1 if delta <= [n+3x(n mod 2)/6] + 1, hc(n, delta) = C(n - [n/2] + 1, 2) + [n/w](2) - [n/2] + 1 if [n+3x(n mod 2)/6] + 1 < delta <= [n/2], and hc(n, delta) = [n delta/2] if delta > [n/2]. (C) 2009 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.aml.2009.03.025
http://hdl.handle.net/11536/6291
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.03.025
期刊: APPLIED MATHEMATICS LETTERS
Volume: 23
Issue: 1
起始頁: 26
結束頁: 29
Appears in Collections:Articles


Files in This Item:

  1. 000272642100006.pdf