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 and be two hamiltonian paths of . We say that and are independent if , and for . We say a set of hamiltonian paths of between two distinct vertices are mutually independent if any two distinct paths in the set are independent. We use to denote the number of vertices and use to denote the number of edges in graph . Moreover, we use to denote the number of edges in the complement of . Suppose that is a graph with and . We prove that there are at least mutually independent hamiltonian paths between any pair of distinct vertices of except and . Assume that is a graph with the degree sum of any two non-adjacent vertices being at least . Let and be any two distinct vertices of . We prove that there are mutually independent hamiltonian paths between and if and there are mutually independent hamiltonian paths between and if otherwise. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|