Constructing MIHCs for Arrangement Graphs A_(n ,k) with n - k ≥ 3

摘要

The arrangement graph A_(n,k) has been used as the underlying topology for many practical multicomputer, and has been extensively studied in the past. The construction scheme of mutually independent hamiltonian cycle, abbreviated as MIHCs, on A_(n,k) has not been done except for two special cases with n- k = 1 and n - k = 2. In this paper, we will prove that any A_(n,k), where n - k ≥ 3 and k ≥ 2, contains k(n - k) MIHCs. More specifically, let N =| V(A_(n,k)) |, v(i) ∈ V{A_(n,k)) for 1 ≤ i ≤ N and (v(1),v(2),... ,v(N),v(1)) be a hamiltonian cycle of A_(n,k). We prove that A_(n,k) contains k(n - k) hamiltonian cycles, denoted by C_l = (v(1),v_l(2), ... ,v_l(N),v(1)) for 1 ≤ 1 ≤ k(n - k), such that v_l(i) ≠ v_l'(i) for 2 ≤ i ≤ N whenever l ≠ l'. The result is optimal since each vertex of A_(n,k) has exactly k(n - k) neighbors.