首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On mutually independent hamiltonian paths
Institution:1. Department of Computer and Information Science, National Chiao Tung University, Hsinchu City 300, Taiwan, ROC;2. Department of Industrial Engineering and Management, Ta Hwa Institute of Technology, Hsinchu County 307, Taiwan, ROC;3. Department of Computer Science and Information Engineering, Ta Hwa Institute of Technology, Hsinchu County 307, Taiwan, ROC
Abstract:Let P1=v1,v2,v3,,vn and P2=u1,u2,u3,,un be two hamiltonian paths of G. We say that P1 and P2 are independent if u1=v1,un=vn, and uivi for 1<i<n. We say a set of hamiltonian paths P1,P2,,Ps 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 ē to denote the number of edges in the complement of G. Suppose that G is a graph with ēn4 and n4. We prove that there are at least n2ē mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and ē=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 degG(u)+degG(v)n mutually independent hamiltonian paths between u and v if (u,v)E(G) and there are degG(u)+degG(v)n+2 mutually independent hamiltonian paths between u and v if otherwise.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号