標題: On mutually independent hamiltonian paths
作者: Teng, YH
Tan, JJM
Ho, TY
Hsu, LH
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian;Hamiltonian connected;Hamiltonian path
公開日期: 1-四月-2006
摘要: Let P-1=< v(1), v(2), v(3),...,v(n)> and P-2=< u(1), u(2), u(3),...,u(n)> be two hamiltonian paths of G. We say that P-1 and P-2 are independent if u(1)=v(1), u(n)=v(n), and u(i)not equal v(i) for 1<i<n. We say a set of hamiltonian paths P-1,P-2,...,P-s of G between two distinct vertices are mutually independent if any two distinct paths in the set are independent. We use n to denote the number of vertices and use e to denote the number of edges in graph G. Moreover, we use (e) over bar to denote the number of edges in the complement of G. Suppose that G is a graph with (e) over bar <= n-4 and n >= 4. We prove that there are at least n-2-(e) over bar mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and (e) over bar =1. Assume that G is a graph with the degree sum of any two non-adjacent vertices being at least n+2. Let u and v be any two distinct vertices of G. We prove that there are deg(G)(u)+deg(G)(v)-n mutually independent hamiltonian paths between u and v if (u, v) is an element of E (G) and there are deg(G)(u)+deg(G)(v)-n+2 mutually independent hamiltonian paths between u and v if otherwise. (C) 2005 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.aml.2005.05.012
http://hdl.handle.net/11536/12432
ISSN: 0893-9659
DOI: 10.1016/j.aml.2005.05.012
期刊: APPLIED MATHEMATICS LETTERS
Volume: 19
Issue: 4
起始頁: 345
結束頁: 350
顯示於類別:期刊論文


文件中的檔案:

  1. 000235784700008.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。