Zhiquan Hu

A graph $G$ is $k$-\emph{linked} if $G$ has at least $2k$ vertices, and for every sequence $(x_{1},x_{2}, \ldots, x_{k}),(y_{1}, y_{2}, \ldots y_{k})$ of distinct vertices, $G$ contains $k$ pairwise disjoint paths $(P_1, P_2, \ldots, P_k)$ such that $P_{i}$ joins $x_{i}$ and $y_{i}$ for $i=1,2,\ldots,k$. Moreover, the above defined $k$-linked graph $G$ is \emph{$k$-linked modulo $(m_{1}, m_{2}, \ldots, m_{k})$ if, in addition, for any $k$-tuple $(d_{1}, d_{2}, \ldots, d_{k})$ of natural numbers, the paths $(P_{1}, P_{2}, \ldots, P_{k})$ can be chosen such that $P_{i}$ has length $d_{i}$ modulo $m_{i}$ for $i=1,2,\ldots,k$. Thomassen showed that there exists a function $f(m_{1}, m_{2}, \ldots, m_{k})$ such that every $f(m_{1}, m_{2}, \ldots, m_{k})$-connected graph is \emph{ modulo $(m_{1}, m_{2}, \ldots, m_{k})$-linked} provided all $m_{i}$ are odd. In another article, he showed that there exists a natural number $g(2,2,\ldots, 2)$ such that every $g(2,2,\ldots, 2)$-connected graph is \emph{ modulo $(2,2, \ldots, 2)$-linked} if the deleting of any $4k-3$ vertices leaves a nonbipartite graph. In this paper, we give linear upper bounds for $f(m_{1}, m_{2}, \ldots, m_{k})$ and $g(m_{1}, m_{2}, \ldots, m_{k})$ in terms of $m_{1}$, $m_{2|$, $\cdots$, $m_{k}$, respectively. More specifically, we prove the following two main results: (i) For any $k$-tuple $(m_{1}, m_{2}, \ldots, m_{k})$ of odd positive integers, every $\max\{14\mkk-4k, 6\mkk-4k+36\}$-connected graph is $k$-linked modulo $(m_{1}, m_{2}, \ldots, m_{k})$. (ii) Let $1\le \ell \le k$ and let $(m_{1}, m_{2}, \ldots, m_{k})$ be a $k$-tuple of positive integers such that $m_{i}$ is odd for each $i$ with $\ell+1\leq i\leq k$. If $G$ is $45(m_1+m_2+\cdots+m_k)$-connected, then either $G$ has a vertex set $X$ of order at most $2k+2\ell-3$ such that $G-X$ is bipartite or $G$ is $k$-linked modulo $(m_{1}',m_{2}',\ldots, m_{k}')$, where \begin{equation} \dis m_i':=\begin{cases} 2m_i, &\text{if}\ \ 1\leq i\leq \ell,\cr m_i, &\text{if} \ \ \ell+1\leq i\leq k. \end{cases} \end{equation} Our results generalize several known results on $k$-parity-linked graphs.