標題: On the extremal number of edges in hamiltonian connected graphs 作者: Ho, Tung-YangLin, Cheng-KuanTan, Jimmy J. M.Hsu, D. FrankHsu, 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.025http://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: