Graph Connectivity And Modulo Linkage

A graph G is said to be k-linked if G has at least 2k vertices, and for every sequence x₁,x₂,..., x_k,y₁ ,y₂, ..., y_k of distinct vertices, G contains k pairwise disjoint paths P₁, P₂,..., P_k such that P_i joins x_i and y_i for i = 1,2,..., k. We say that G is modulo (m₁, m₂,..., linked if G is k-linked and, in addition, for any k-tuple (d₁, d₂,..., of natural numbers, the paths P₁, P₂,..., P_k can be chosen such that P_i has length d_i modulo m_i for i = 1,2,..., k. Thomassen [20] show that if each m_i is odd and G has sufficiently high connectivity then G is modulo (m1_, m₂,..., m_k)-linked. In this paper, we will show that the above statement is still valid for every connected graph if each m_i is an odd number .