標題: | 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 |
顯示於類別: | 期刊論文 |