On mutually independent hamiltonian paths

Abstract

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.