On Modulo Linked Graphs

A graph G is said to be k-linked if G has at least 2k vertices, and for every sequence x1,X2,...,xk,y1,y2,... ,yk of distinct vertices, G contains k pairwise disjoint paths P1, P2,..., Pk such that Pi joins xi and yi for i = 1,2,..., k. We say that G is modulo (m1,m2, ..., mk)-linked if G is k-linked and, in addition, for any k-tuple (d1, d2,..., dk) of natural numbers, the paths P1,P2,...,Pk can be chosen such that Pi has length di modulo mi for i = 1,2,..., k. Thomassen [14] show that if each mi is odd and G has sufficiently high connectivity then G is modulo (m1,m2,..., mk)-linked.In this paper, we will show that the above statement is still valid for max{14(m1 + m2 + ... + mk) - 4k, 50}-connected graphs if each mi is an odd prime, we also prove that G is (92 ∑_i~k=1 mi - 44k)-connected, where mi is a prime or mi = 1, Then either G is modulo (2m1, 2m2,..., 2mk)-linked or G has a vertex set X of order at most 4k — 3 such that G — X is bipartite.