Vertex-Disjoint Paths in Graphs

Abstract

Let $n_1,n_2,\dots ,n_k$ be integers of at least two. Johansson gave a minimum degree condition for a graph of order exactly $n_1+n_2+\cdots +n_k$ to contain $k$ vertex-disjoint paths of order $n_1,n_2,\dots ,n_k$, respectively. In this paper, we extend Johansson’s result to a corresponding packing problem as follows. Let $G$ be a connected graph of order at least $n_1+n_2+\cdots +n_k$. Under this notation, we show that if the minimum degree sum of three independent vertices in $G$ is at least:

$$3(\lfloor \frac{n_1}{2}\rfloor +\lfloor \frac{n_2}{2}\rfloor +\dots +\lfloor \frac{n_k}{2}\rfloor )$$

then $G$ contains $k$ vertex-disjoint paths of order $n_1,n_2,\dots ,n_k$, respectively, or else $n_1=n_2=\cdots =n_e=3$, or $k=2$ and $n_1=n_2=\text{odd}$. The graphs in the exceptional cases are completely characterized. In particular, these graphs have more than $n_1+n_2+\cdots +n_k$ vertices.