The paths embedding of the arrangement graphs with prescribed vertices in given position

摘要

Let n and k be positive integers with n - k ≥ 2. The arrangement graph An,k is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of An,k. Let l be any integer with dAn,k (x, y) ≤ l ≤ n! (n-k)! - 1 - dAn,k (y, z). We shall prove the following existance properties of Hamiltonian path: (1) for n-k ≥ 3 or (n, k) = (3, 1), there exists a Hamiltonian path R(x, y, z; l) from x to z such that dR(x,y,z;l)(x, y) = l; (2) for n-k = 2 and n ≥ 5, there exists a Hamiltonian path R(x, y, z; l) except for the case that x, y, and z are adjacent to each other.