# On the path partition of graphs

Mekkia Kouider Université Paris Sud, France<EMAIL_ADDRESS>Mohamed Zamime Faculty
of Technology, University of Medea, Algeria<EMAIL_ADDRESS>
###### Abstract

Let $\displaystyle G$ be a graph of order $\displaystyle n$. The maximum and
minimum degree of $\displaystyle G$ are denoted by $\displaystyle\Delta$ and
$\displaystyle\delta$ respectively. The _path partition number_
$\displaystyle\mu(G)$ of a graph $\displaystyle G$ is the minimum number of
paths needed to partition the vertices of $\displaystyle G$. Magnant, Wang and
Yuan conjectured that
$\displaystyle\mu(G)\leq\max\left\\{\frac{n}{\delta+1},\frac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}\right\\}.$
In this work, we give a positive answer to this conjecture, for
$\displaystyle\Delta\geq 2\delta$.

###### keywords:

path, partition.
2010 Mathematics Subject Classification: 05C20

##  1 Introduction

Throughout the paper, all graphs are finite, simple and undirected. Let
$\displaystyle G$ be a graph with vertex-set $\displaystyle V(G)$ and edge-set
$\displaystyle E(G).$ We denote by $\displaystyle n$ the order of
$\displaystyle G.$ The _neighborhood_ of a vertex $\displaystyle v\in V$ is
$\displaystyle N\left(v\right)=\left\\{u\in V:uv\in E\right\\}.$ The _degree_
of $\displaystyle v,$ denoted by $\displaystyle d\left(v\right),$ is the size
of its neighborhood. The _minimum degree_ of the graph $\displaystyle G$ is
denoted by $\displaystyle\delta(G)$, and the _maximum degree_ by
$\displaystyle\Delta(G).$

Let $\displaystyle A$ and $\displaystyle B$ be two subsets of $\displaystyle
V(G)$. Let $\displaystyle\varepsilon(A,B)$ be the number of edges with one end
vertex in the set $\displaystyle A$ the other one in the set $\displaystyle
B$.

In this work, we deal with the partition problem. The cover problem and the
partition problem constitute a large and important class of well studied
problems in the fields of graph theory. A cycle cover of a graph (resp. a path
cover) is a set $\displaystyle\mathcal{C}$ of cycles (resp. paths) of the
graph such that each vertex belongs to at least one cycle (resp. one path) of
$\displaystyle\mathcal{C}$. Many results on these concepts, have been given in
the literature. For example, Kouider [6][7], and Kouider and Lonc [8] studied
the problem of covering a graph by a minimum number of cycles. More details
and references can be found in the survey of Manuel [13].

Among the many variations of the partition problem, we mention the _path
partition_ that has been studied intensively for about sixty years. A family
$\displaystyle\mathcal{P}$ of paths is called a _path partition_ of a graph
$\displaystyle G$ if its members cover the vertices of the graph and are
vertex disjoint. Its cardinality $\displaystyle\left|\mathcal{P}\right|$ is
the number of paths of $\displaystyle\mathcal{P}.$ The _path partition number_
of $\displaystyle G$ is
$\displaystyle\mu(G)=\min\\{\left|\mathcal{P}\right|:\mathcal{P}$ is a path
partition of $\displaystyle G\\}.$ The concept of path partition number was
introduced by Ore [14] in $\displaystyle 1961$. Several works have been done
in this topic. See for example [1, 2, 4].

In $\displaystyle 1996$, Reed proved the folowing result [15].

######  Theorem 1.

[15] Let $\displaystyle G$ be a connected cubic graph on $\displaystyle n$
vertices. Then
$\displaystyle\mu(G)\leq\left\lceil\frac{n}{9}\right\rceil.$

Furthermore, for $\displaystyle 2$-connected graphs, a better bound is
established by Yu[16].

######  Theorem 2.

Let $\displaystyle G$ be a $\displaystyle 2$-connected cubic graph on
$\displaystyle n$ vertices. Then
$\displaystyle\mu(G)\leq\left\lceil\frac{n}{10}\right\rceil.$

For regular graphs, in $\displaystyle 2009$, Magnant and Martin [11]
conjectured the following.

######  Conjecture 1.

[11] Let $\displaystyle G$ be a $\displaystyle d$-regular graph on
$\displaystyle n$ vertices.
Then $\displaystyle\mu(G)\leq\frac{n}{d+1}.$

They verified this last conjecture for the case $\displaystyle d\leq 5$ (see
[11]). In $\displaystyle 2018$, Han has an asymptotic answer.

######  Theorem 3.

[4] For every $\displaystyle c,$ $\displaystyle 0<c<1$ and
$\displaystyle\alpha>0$, there exists $\displaystyle n_{0}$ such that if
$\displaystyle n\geq n_{0}$, $\displaystyle d\geq cn$ and $\displaystyle G$ is
a $\displaystyle d$-regular graph on $\displaystyle n$ vertices, then
$\displaystyle n/(d+1)$ vertex-disjoint paths cover all vertices of
$\displaystyle G$ except $\displaystyle\alpha n$.

Gruskys and Letzter [3] improve this result by allowing to take
$\displaystyle\alpha=0.$

In $\displaystyle 2016$, Magnant, Wang and Yuan[12] extend Conjecture 1 to
general graphs as follows.

######  Conjecture 2.

[12] Let $\displaystyle G$ be a graph on $\displaystyle n$ vertices. Then

$\mu(G)\leq\max\left\\{\dfrac{n}{\delta+1},\dfrac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}\right\\}.$

If true, the last conjecture would be sharp. For
$\displaystyle\delta+2\leq\Delta,$ the bound is achieved by the collection of
disjoint copies of $\displaystyle K_{\delta,\Delta}.$ For
$\displaystyle\delta=\Delta,$ it is achieved by the collection of disjoint
copies of complete graphs $\displaystyle K_{\delta+1}.$ This conjecture is
proved in [12] for the case $\displaystyle\delta=1$ and
$\displaystyle\delta=2.$
In this work, we prove Conjecture 2 for all graphs with maximum degree
$\displaystyle\Delta$ at least $\displaystyle 2\delta.$

######  Theorem 4.

Let $\displaystyle G$ be a graph of order $\displaystyle n$ of minimum degree
$\displaystyle\delta,(\delta\geq 2),$ and maximum degree $\displaystyle\Delta$
with $\displaystyle\Delta\geq 2\delta.$ Then
$\displaystyle\mu(G)\leq\dfrac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}.$

We remark that
$\displaystyle\dfrac{n}{\delta+1}\leq\dfrac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}$
if and only if $\displaystyle\delta+2\leq\Delta.$ So for
$\displaystyle\delta\geq 2$ and $\displaystyle\Delta\geq 2\delta$, the
inequality of the theorem is equivalent to

$\mu(G)\leq\max\left\\{\dfrac{n}{\delta+1},\dfrac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}\right\\}$

which is the inequality of the Conjecture 2.

##  2 Preliminaries

Let us introduce the following notations and definitions. Let
$\displaystyle\mathcal{P}$ be a minimum path partition of $\displaystyle
V(G)$. So, $\displaystyle\left|\mathcal{P}\right|=\mu(G)$. Let $\displaystyle
p_{i}$ be the number of paths of order $\displaystyle i\in\\{1,2\\}$ in
$\displaystyle\mathcal{P}.$
We may suppose that $\displaystyle p_{1}+p_{2}\neq 0,$ otherwise we have
$\displaystyle\mu(G)\leq\frac{n}{3}$. As $\displaystyle\Delta\geq 2\delta$, we
get
$\displaystyle\mu(G)\leq\dfrac{\left(\Delta-\delta\right)n}{\left(\Delta+\delta\right)}$
and the problem is resolved.
Let $\displaystyle V_{1}$ be the set of isolated vertices of
$\displaystyle\mathcal{P}$ and $\displaystyle V_{2}$ be the set of end
vertices of the isolated edges of $\displaystyle\mathcal{P}$. We denote by
$\displaystyle R$ any path in $\displaystyle\mathcal{P}$, and we write
$\displaystyle R=R[a,b]=[a,...,b]$ if $\displaystyle a$ and $\displaystyle b$
are the end vertices of $\displaystyle R$. We set $\displaystyle
End(R)={\\{a,b\\}.}$ Let $\displaystyle Int\left(R\right)$ be the set of
internal vertices of $\displaystyle R$. Let $\displaystyle\mathcal{A}$
$\displaystyle\subseteq{\mathcal{P}}$. We denote by $\displaystyle
Int(\mathcal{A})$ (resp. $\displaystyle End(\mathcal{A})$) the set of internal
(resp. end ) vertices of the paths of $\displaystyle\mathcal{A}$. For
$\displaystyle i$ fixed, we denote by $\displaystyle R_{i}$ any path of order
$\displaystyle i$. We set $\displaystyle{\mathcal{R}}_{i}$ the set of paths of
order $\displaystyle i$. By $\displaystyle abcd$ or $\displaystyle[a,b,c,d]$
we denote a path with $\displaystyle 4$ vertices. For $\displaystyle i$ odd,
$\displaystyle i\geq 3$, let us set $\displaystyle
C_{i}=\bigcup\limits_{R\in\mathcal{R}_{i}}c\left(R\right)$, where
$\displaystyle c\left(R\right)$ denotes the central vertex of the path
$\displaystyle R$.

######  Example 1.

Let us illustrate the above notations relative to a partition in Figure 1.

$\displaystyle x_{1}$$\displaystyle x_{2}$$\displaystyle x_{3}$$\displaystyle
x_{4}$$\displaystyle x_{5}$$\displaystyle x_{6}$$\displaystyle
x_{7}$$\displaystyle x_{8}$$\displaystyle w_{1}$$\displaystyle
x_{9}$$\displaystyle x_{10}$$\displaystyle w_{2}$$\displaystyle
x_{11}$$\displaystyle x_{12}$$\displaystyle w_{3}$$\displaystyle
w_{4}$$\displaystyle x_{13}$$\displaystyle x_{14}$$\displaystyle
w_{5}$$\displaystyle x_{15}$$\displaystyle x_{16}$$\displaystyle
w_{6}$$\displaystyle x_{17}$$\displaystyle x_{18}$$\displaystyle
w_{7}$$\displaystyle x_{19}$$\displaystyle x_{20}$$\displaystyle
w_{8}$$\displaystyle x_{21}$ Figure 1: Illustration of the definitions

$\displaystyle{\mathcal{R}}_{1}=\left\\{x_{1}\right\\},$
$\displaystyle{\mathcal{R}}_{2}=\left\\{\left[x_{2},x_{3}\right],\text{
}\left[x_{4},x_{5}\right],\text{ }\left[x_{6},x_{7}\right]\right\\},$
$\displaystyle{\mathcal{R}}_{3}=\left\\{\left[x_{8},.,x_{9}\right]\right\\}$,
$\displaystyle{\mathcal{R}}_{4}=\left\\{\left[x_{10},..,x_{11}\right],\left[x_{12},..,x_{13}\right]\right\\},$
$\displaystyle{\mathcal{R}}_{5}=\left\\{\left[x_{14},..,x_{15}\right],\left[x_{16},..,x_{17}\right],\left[x_{18},..,x_{19}\right],\left[x_{20},..,x_{21}\right]\right\\}.$
$\displaystyle
End({\mathcal{R}}_{3})=\left\\{x_{8},x_{9}\right\\},End({\mathcal{R}}_{4})=\left\\{x_{10},x_{11},x_{12},x_{13}\right\\},$
$\displaystyle
End({\mathcal{R}}_{5})=\left\\{x_{14},x_{15},x_{16},x_{17},x_{18},x_{19},x_{20},x_{21}\right\\}.$
$\displaystyle C_{3}=\left\\{w_{3}\right\\},$ $\displaystyle
C_{5}=\left\\{w_{5},w_{6},w_{7},w_{8}\right\\}.$

For $\displaystyle x\in End(R),$ $\displaystyle N_{ext}\left(x\right)$ is the
set of non path neighbors (neighbors of $\displaystyle x$ outside its own path
$\displaystyle R$) and $\displaystyle N_{ext}(X^{\prime})=\bigcup\limits_{x\in
X^{\prime}}N_{ext}(x)$ with $\displaystyle X^{\prime}\subset
End(\mathcal{P}).$ Now using $\displaystyle N_{ext}(V_{1}\cup V_{2})$, we
define a subset $\displaystyle X$ of $\displaystyle End(\mathcal{P})$ and we
denote $\displaystyle N_{ext}(X)$ by $\displaystyle W.$ Let $\displaystyle
X_{1}=V_{1}\cup V_{2},$ $\displaystyle W_{1}=N_{ext}\left(X_{1}\right)$ and
for $\displaystyle t\geq 1,$ $\displaystyle X_{t}$ being defined, let

$X_{t+1}=X_{t}\cup(\bigcup\limits_{N_{ext}(X_{t})\cap
Int(R)\neq\emptyset,R\in\mathcal{R}}End(R)).$ (1)

Let $\displaystyle s\geq 1$ the first integer such that $\displaystyle
X_{s}=X_{s+1}$. Let us set $\displaystyle X=X_{s},$ $\displaystyle
W=N_{ext}\left(X\right)$ and for $\displaystyle t\in\\{1,...,s\\},$ let
$\displaystyle W_{t+1}=N_{ext}\left(X_{t+1}\right)\backslash
N_{ext}\left(X_{t}\right).$ Then $\displaystyle
W=\bigcup\limits_{i=1}^{i=s}W_{i}.$ Here is an example of that construction.

######  Example 2.

For the partition in Figure 1, we have $\displaystyle
X_{1}=\\{x_{1},x_{2},...,x_{7}\\}$,
$\displaystyle X_{2}=X_{1}\cup\\{x_{8},x_{9},...,x_{15}\\}$, $\displaystyle
X_{3}=X_{2}\cup\\{x_{16},x_{17},x_{18},x_{19}\\}$, $\displaystyle
X_{4}=X_{3}\cup\\{x_{20},x_{21}\\}=X$, $\displaystyle
W_{1}=\\{w_{1},w_{2},...,w_{5}\\}$, $\displaystyle W_{2}=\\{w_{6},w_{7}\\}$,
$\displaystyle W_{3}=\\{w_{8}\\}$ and $\displaystyle
W=\\{w_{1},w_{2},...,w_{8}\\}$.

Let $\displaystyle X_{0}=\emptyset.$ Pick $\displaystyle w_{r}\in W_{r}$ for
some $\displaystyle r$. By definition of $\displaystyle w_{r}$, there exists a
sequence

$\alpha\left(w_{r}\right)=x_{1}w_{1},x_{2}w_{2},...,x_{r}w_{r},$ (2)

where for each $\displaystyle t\in\left\\{1,...,r\right\\}$, $\displaystyle
x_{t}\in X_{t}-X_{t-1}$, $\displaystyle w_{t}\in W_{t}$ and $\displaystyle
x_{t}w_{t}$ is an edge joining two paths of the partition. In addition, for
each $\displaystyle t\in\left\\{1,...,r-1\right\\}$, $\displaystyle w_{t}$ and
$\displaystyle x_{t+1}$ are in the same path of the partition.

_The sequence_ $\displaystyle\alpha(w_{r})$_has a good order_ if the vertex
$\displaystyle w_{r}$ belongs to a path $\displaystyle R$ with end vertices,
say $\displaystyle x_{r+1}$ and $\displaystyle x_{r+1}^{\prime}$, in
$\displaystyle X_{r+1}-X_{r}.$ _The vertex_ $\displaystyle w_{r}$_is then said
to be of good order_. Using a sequence $\displaystyle\alpha(w_{r})$ with _good
order_ , we can define two new partitions as follows.

For each $\displaystyle i\in\\{1,...,r+1\\},$ we orient the paths of
$\displaystyle\mathcal{P}$ such that each $\displaystyle x_{i}$ is the
terminal extremity. We denote by $\displaystyle w_{t}^{+}$ and $\displaystyle
w_{t}^{-}$ the successor and the predecessor of $\displaystyle w_{t},$
respectively.

1) $\displaystyle\mathcal{P}_{1}\left(w_{r}\right)$ is obtained from
$\displaystyle\mathcal{P}$ by deleting the edges $\displaystyle
w_{t}w_{t}^{+},$ $\displaystyle 1\leq t\leq r$ and adding the edges
$\displaystyle x_{t}w_{t}$ for $\displaystyle 1\leq t\leq r;$

2) $\displaystyle\mathcal{P}_{2}\left(w_{r}\right)$ is obtained from
$\displaystyle\mathcal{P}$ by deleting the edges $\displaystyle
w_{t}w_{t}^{+},$ $\displaystyle 1\leq t\leq r-1$ and the edge $\displaystyle
w_{r}w_{r}^{-}$ and adding the edges $\displaystyle x_{t}w_{t}$ for
$\displaystyle 1\leq t\leq r$.

If we consider the sets of edges of these partitions we note that

$E(\mathcal{P}_{2})=(E(\mathcal{P}_{1})-w_{r}w_{r}^{-})\cup w_{r}w_{r}^{+}.$

Furthermore, $\displaystyle|\mathcal{P}_{2}|=|\mathcal{P}_{1}|=\mu(G).$

$\displaystyle x^{\prime}_{1}$$\displaystyle x_{1}$$\displaystyle
w^{-}_{1}$$\displaystyle w_{1}$$\displaystyle w^{+}_{1}$$\displaystyle
x_{2}$$\displaystyle x_{3}$$\displaystyle w^{+}_{2}$$\displaystyle
w_{2}$$\displaystyle w^{-}_{2}$$\displaystyle x^{\prime}_{3}$$\displaystyle
x^{\prime}_{4}$$\displaystyle w^{-}_{3}$$\displaystyle w_{3}$$\displaystyle
w^{+}_{3}$$\displaystyle x_{4}$ Figure 2: Graph with $\displaystyle\mu(G)=4$

For example, the sequence $\displaystyle\alpha(w_{2})$ in the graph of Figure
2, defines two partitions.
We have
$\displaystyle\mathcal{P}_{1}\left(w_{2}\right)=\left\\{x_{1}^{\prime}x_{1}w_{1}w_{1}^{-},w_{1}^{+}x_{2}w_{2}w_{2}^{-}x_{3}^{\prime},x_{3}w_{2}^{+},x_{4}^{\prime}w_{3}^{-}w_{3}w_{3}^{+}x_{4}\right\\}$
and
$\displaystyle\mathcal{P}_{2}\left(w_{2}\right)=\left\\{x_{1}^{\prime}x_{1}w_{1}w_{1}^{-},w_{1}^{+}x_{2}w_{2}w_{2}^{+}x_{3},w_{2}^{-}x_{3}^{\prime},x_{4}^{\prime}w_{3}^{-}w_{3}w_{3}^{+}x_{4}\right\\}.\vskip
3.0pt plus 1.0pt minus 1.0pt$

We denote by $\displaystyle R_{i}[x^{\prime},x]$ any path of order
$\displaystyle i$ oriented from $\displaystyle x^{\prime}$ to $\displaystyle
x.$ So $\displaystyle x^{\prime}$ is the initial end of $\displaystyle R_{i}$
and $\displaystyle x$ is its terminal end.

######  Observation 1.

If $\displaystyle w\in W_{t},$ then for some $\displaystyle i,$ $\displaystyle
w$ belongs to some path $\displaystyle R_{i}\left[x^{\prime},x\right].$ The
path $\displaystyle R_{i_{1}}\left[w^{+},x\right]$ is in
$\displaystyle\mathcal{P}_{1}\left(w\right)$ and the path $\displaystyle
R_{i_{2}}\left[x^{\prime},w^{-}\right]$ is in
$\displaystyle\mathcal{P}_{2}\left(w\right).$ Note that the subpath
$\displaystyle R_{i_{1}}\left[w^{+},x\right]$ (resp. $\displaystyle
R_{i_{2}}\left[x^{\prime},w^{-}\right])$ is of order $\displaystyle i_{1}$
(resp. $\displaystyle i_{2})$ such that $\displaystyle i_{1}+i_{2}+1=i.\vskip
12.0pt plus 4.0pt minus 4.0pt$

##  3 Proof of Theorem 4 :

We choose a minimum path-partition $\displaystyle\mathcal{P}_{0}$ such that
1) $\displaystyle p_{1}$ is minimum,
2) if (1) is satisfied, then $\displaystyle p_{2}$ is minimum.
Let $\displaystyle\mathcal{P}^{\prime}$ be the set of paths with end vertices
in $\displaystyle X$. Let $\displaystyle p=|\mathcal{P}^{\prime}|.$ Let
$\displaystyle p_{i}$ be the number of paths of order $\displaystyle i$ in
$\displaystyle\mathcal{P}^{\prime}.$

Sketch of the proof
In view to bound $\displaystyle\mu(G)$ we want to bound $\displaystyle p_{1}$
and $\displaystyle p_{2}$. We consider the set $\displaystyle X$ generated by
$\displaystyle V_{1}\cup V_{2}$, and therefore the two sets $\displaystyle
W=N_{ext}(X)$ and $\displaystyle\varepsilon(X,W)$. Note that the cardinality
of $\displaystyle X$ is $\displaystyle 2p-p_{1}$, The proof of our theorem is
done through the following steps. We want to bound in two manners the number
of edges $\displaystyle\varepsilon(X,W).$ The upper bound will use
$\displaystyle W$ and $\displaystyle\Delta$, the lower bound will use
$\displaystyle X$ and $\displaystyle\delta$.
In the first part of the proof, we show some claims relative to the set
$\displaystyle W$ and one relative to the lower bound of
$\displaystyle\varepsilon(x,W)$ for $\displaystyle x\in X.$ In the second part
of the proof, we calculate the bounds of $\displaystyle\varepsilon(X,W)$. We
get finally an upper bound for $\displaystyle p_{1}+2p_{2}$ in function of
$\displaystyle p,\delta$ and $\displaystyle\Delta$, and, then an upper bound
for $\displaystyle\mu(G)$.

A) Claims

######  Claim 1.

  1. 1.

For each $\displaystyle v\in V_{1},$ $\displaystyle N(v)\subset C_{3}$.

  2. 2.

For each $\displaystyle a\in V_{2},$ $\displaystyle N(a)\subset C_{3}\cup
Int(\mathcal{R}_{4})\cup C_{5}.$

So, $\displaystyle\left\\{\begin{array}[]{c}\left|N\left(a\right)\cap
R\right|\leq 1,\text{ for every path }R\text{ of order }3\text{ or }5.\\\
\left|N\left(a\right)\cap R\right|\leq 2,\text{ \ \ \ \ \ \ for every path
}R\text{ of order }4.\end{array}\right..$

###### Proof of Claim 1.

1) Let $\displaystyle v$ be a vertex of $\displaystyle V_{1}$. By the
minimality of $\displaystyle\mathcal{P}_{0}$, $\displaystyle v$ is not
adjacent to an end vertex of another path in $\displaystyle\mathcal{P}_{0}$.
Let $\displaystyle w$ be a neighbor of $\displaystyle v$ in a path oriented
from $\displaystyle x^{\prime}$ to $\displaystyle x.$ We have two partitions.
In $\displaystyle\mathcal{P}_{0}$, we replace the path $\displaystyle v$ and
the path $\displaystyle R_{i}\left[x^{\prime},x\right]$ either by the pair of
paths $\displaystyle vR_{i_{1}}\left[w,x\right],$ $\displaystyle
R_{i_{2}}\left[x^{\prime},w^{-}\right]$ or by the pair of paths $\displaystyle
R_{i_{1}^{\prime}}\left[x^{\prime},w\right]v,$ $\displaystyle
R_{i_{2}^{\prime}}\left[w^{+},x\right].$ By the minimality of $\displaystyle
p_{1}$, w is both predecessor of x and successor of $\displaystyle
x^{\prime}$. So the order of $\displaystyle R_{i}\left[x^{\prime},x\right]$ is
$\displaystyle 3,$ and $\displaystyle w$ is the center of $\displaystyle
R_{i}\left[x^{\prime},x\right]$. Thus $\displaystyle N\left(v\right)\subset
C_{3}.$
2) Let $\displaystyle w$ be a neighbor of $\displaystyle a$ in $\displaystyle
R_{i}\left[x^{\prime},x\right].$ As precedently, we get two partitions and by
definition of $\displaystyle\mathcal{P}_{0}$, each of $\displaystyle
R_{i}\left[x^{\prime},w^{-}\right]$ and $\displaystyle
R_{i}\left[w^{+},x\right]$ should be of order at most two. So $\displaystyle
N\left(a\right)\subset C_{3}\cup C_{5}\cup Int\left(\mathcal{R}_{4}\right),$
completing the proof of Claim 1 ∎

######  Claim 2.

Let $\displaystyle W_{a}$ be the set of vertices of good order in
$\displaystyle W.$ Then

  1. 1.

$\displaystyle W_{a}\subset C_{3}\cup Int\left(\mathcal{R}_{4}\right)\cup
C_{5}.$

  2. 2.

$\displaystyle W=W_{a}.$

###### Proof of Claim 2.

1) Suppose that there exists $\displaystyle w\in W_{a}$ such that
$\displaystyle w$ is in the path $\displaystyle
R_{i}\left[x^{\prime},x\right].$ By Observation 1, we have $\displaystyle
i-1=i_{1}+i_{2}$. If $\displaystyle i_{1}\geq 3$ (resp. $\displaystyle
i_{2}\geq 3)$, then $\displaystyle\mathcal{P}_{1}\left(w\right)$ (resp.
$\displaystyle\mathcal{P}_{2}\left(w\right)$) contains $\displaystyle p_{1}-1$
paths of order $\displaystyle 1$ or $\displaystyle p_{1}$ paths of order
$\displaystyle 1$ and $\displaystyle p_{2}-1$ paths of order $\displaystyle
2$. A contradiction with the definition of $\displaystyle\mathcal{P}_{0}.$
Thus $\displaystyle W_{a}\subset C_{3}\cup Int\left(\mathcal{R}_{4}\right)\cup
C_{5}.$

2) Suppose that $\displaystyle W\neq W_{a}.$ In $\displaystyle
W_{b}=W\backslash W_{a}$ there exists necessarely a vertex $\displaystyle
w=w_{r}$ with sequence
$\displaystyle\alpha\left(w\right)=x_{1}w_{1},x_{2}w_{2},...,x_{r}w_{r}$ with
$\displaystyle x_{t}\in X_{t}-X_{t-1}$ $\displaystyle x_{r}$ is an end vertex
of some path $\displaystyle R=\left[x_{r}^{\prime},...,x_{r}\right].$ By the
definition of $\displaystyle w$, the vertex $\displaystyle w$ belongs to a
path $\displaystyle R^{\prime}=[x_{j}^{\prime},...,x_{j}]$ with $\displaystyle
x_{j}\in X_{j},$ $\displaystyle j\leq r.$ By the definition of $\displaystyle
X_{j},$ the path $\displaystyle R^{\prime}$ contains one element of
$\displaystyle W_{a}$, say $\displaystyle w_{a}.$ By the definition of
$\displaystyle W_{a}$, $\displaystyle w_{a}$ is adjacent to a vertex
$\displaystyle x^{\prime\prime}$ of $\displaystyle X_{j-1},$ end vertex of a
path $\displaystyle R^{\prime\prime}$. Since $\displaystyle W_{a}\subset
C_{3}\cup Int\left(\mathcal{R}_{4}\right)\cup C_{5},$ then
$\displaystyle\left|R^{\prime}\right|=4$ or $\displaystyle 5$ and
$\displaystyle w=w_{a}^{-}$ or $\displaystyle w=w_{a}^{+}.$ The end vertex
$\displaystyle x_{r}\in X_{r}$ and the end vertex $\displaystyle
x^{\prime\prime}\in X_{j-1}$ are adjacent respectively to $\displaystyle w$
and $\displaystyle w_{a}$, successive vertices of the same path $\displaystyle
R^{\prime}$.

$\displaystyle x^{\prime}_{r}$$\displaystyle x_{r}$$\displaystyle
x^{\prime}_{j}$$\displaystyle x_{j}$$\displaystyle
x^{\prime}_{j-1}$$\displaystyle x^{\prime\prime}$$\displaystyle
w$$\displaystyle w_{a}$$\displaystyle R$$\displaystyle
R^{\prime\prime}$$\displaystyle R^{\prime}$ Figure 3: Paths $\displaystyle R$,
$\displaystyle R^{\prime}$, $\displaystyle R^{\prime\prime}$

We get a partition with $\displaystyle p-1$ paths. We replace the three paths
$\displaystyle R,$ $\displaystyle R^{\prime}$ and $\displaystyle
R^{\prime\prime}$ by the two paths composed by $\displaystyle R\cup
R^{\prime}\cup
R^{\prime\prime}\cup\\{x_{r}w,x^{\prime\prime}w_{a}\\}-~{}\\{ww_{a}\\}$ (see
Figure 3), a contradiction with the minimality of
$\displaystyle\mathcal{P}_{0}.$ Thus, $\displaystyle W_{b}=\emptyset$ and so,
$\displaystyle W=W_{a}.$ This completes the proof of Claim 2. ∎

######  Claim 3.

For each path $\displaystyle R$ of order $\displaystyle 4$ in
$\displaystyle\mathcal{P}_{0},$ we have $\displaystyle\left|W\cap
V\left(R\right)\right|\leq 2.$ Furthermore if $\displaystyle\left|W\cap
V\left(R\right)\right|=2$, then there is a unique $\displaystyle x\in X$ such
that $\displaystyle W\cap V\left(R\right)\neq\emptyset$ and thus
$\displaystyle\varepsilon(X,R)=4$

###### Proof of Claim 3.

By the minimality of $\displaystyle\mathcal{P}_{0}$ for each path
$\displaystyle R\in\mathcal{R}_{4}$, we have $\displaystyle\left|W\cap
V\left(R\right)\right|\leq 2$. Now, assume that there exists a path
$\displaystyle R\in\mathcal{R}_{4}$ such that $\displaystyle W\cap
V\left(R\right)=\left\\{w_{1},w_{2}\right\\}$ where $\displaystyle w_{i}\in
N_{ext}\left(x_{i}\right),$ $\displaystyle i=1,$ $\displaystyle 2.$ By taking
off the edge $\displaystyle w_{1}w_{2}$ and adding the edges $\displaystyle
x_{1}w_{1}$ and $\displaystyle x_{2}w_{2}$ we obtain a partition with
$\displaystyle p-2$ paths, a contradiction. So $\displaystyle x_{1}=x_{2}.$
Let $\displaystyle R^{\prime}(x_{1})$ be the path of extremity $\displaystyle
x_{1}$ in the partition. We may suppose $\displaystyle
R=[x_{0}^{\prime},w_{1},w_{2},x_{0}]$. If $\displaystyle x_{0}$ is neighbor of
$\displaystyle w_{1}$, then we replace the two paths $\displaystyle R$ and
$\displaystyle R^{\prime}(x_{1})$ by the path $\displaystyle
R^{\prime}(x_{1})\cup[w_{2},x_{0},w_{1},x^{\prime}_{0}]$. We get a partition
with $\displaystyle p-1$ paths, a contradiction. So, there is no edge
$\displaystyle x_{0}w_{1}$. Similarly, there is no edge $\displaystyle
x_{0}^{\prime}w_{2}$. It follows that $\displaystyle\varepsilon(X,R)=4$,
completing the proof of Claim 3 ∎

For $\displaystyle i\in\left\\{1,2\right\\},$ let
$\displaystyle\mathcal{R}_{4}^{i}$ be the set of paths of order $\displaystyle
4$, which contain exactly $\displaystyle i$ elements of $\displaystyle W$.
For the lower bound we shall need the following claim.

######  Claim 4.

  1. 1.

If $\displaystyle x\in X\cap V(\mathcal{R}_{1}\cup\mathcal{R}_{3})$, then
$\displaystyle x$ has $\displaystyle d(x)$ neighbors in $\displaystyle W$.

  2. 2.

If $\displaystyle x_{1},$ $\displaystyle x_{2}\in X\cap V(\mathcal{R}_{4}),$
then the set $\displaystyle\\{x_{1},x_{2}\\}$ has $\displaystyle
d(x_{1})+d(x_{2})-1$ neighbors in $\displaystyle W$ if $\displaystyle x_{1},$
$\displaystyle x_{2}$ belong to
$\displaystyle{V}\left({\mathcal{R}_{4}^{1}}\right)$ and it has $\displaystyle
d(x_{1})+d(x_{2})$ neighbors if $\displaystyle x_{1},$ $\displaystyle x_{2}$
belong to $\displaystyle{V}\left({\mathcal{R}_{4}^{2}}\right)$.

  3. 3.

If $\displaystyle x\in X\cap V(\mathcal{R}_{2}\cup\mathcal{R}_{5})$, then
$\displaystyle x$ has $\displaystyle d(x)-1$ neighbors in $\displaystyle W$.

###### Proof of Claim 4.

1) If $\displaystyle x\in V_{1},$ then by Claim $\displaystyle 1$,
$\displaystyle N\left(x\right)\subset W.$ If $\displaystyle x\in X\cap
V\left(\mathcal{R}_{3}\right),$ then let $\displaystyle R=xyx^{\prime}.$ By
the minimality of $\displaystyle\mu$, $\displaystyle x$ and $\displaystyle
x^{\prime}$ are not adjacent. It follows that $\displaystyle
N\left(x\right)\subset$$\displaystyle W$. 2) Let $\displaystyle
R^{\prime}=x_{1}yzx_{2}.$ By the minimality of $\displaystyle p_{2},$ there is
no edge $\displaystyle x_{1}x_{2}.$
If $\displaystyle W\cap R^{\prime}=\left\\{y\right\\}$ then $\displaystyle
x_{1}z\notin E\left(G\right)$ by the minimality of the path partition. It
follows that $\displaystyle N\left(x_{1}\right)\subset$$\displaystyle W$ and
$\displaystyle(N\left(x_{2}\right)-\left\\{z\right\\})\subset W$.
If $\displaystyle W\cap V\left(R^{\prime}\right)=\left\\{y,z\right\\},$ then
$\displaystyle N\left(x_{1}\right)\subset W$ and $\displaystyle
N\left(x_{2}\right)\subset W.$
3) Clearly if $\displaystyle x\in V_{2}$, then $\displaystyle x$ has
$\displaystyle d\left(x\right)-1$ neighbors in $\displaystyle W.$
Let $\displaystyle R^{\prime\prime}=x_{1}yztx_{2}.$ By Claim 2, we have
$\displaystyle W\cap V\left(R^{\prime\prime}\right)=\left\\{z\right\\}.$ It
follows that $\displaystyle N\left(x_{1}\right)-\left\\{y\right\\}\subset w$
and $\displaystyle N\left(x_{2}\right)-\left\\{t\right\\}\subset W,$
completing the proof of Claim 4. ∎

Now we bound first $\displaystyle|\mathcal{P}^{\prime}|$ then
$\displaystyle\mu(G).$

B) Calculations of the bounds
1) Bound of $\displaystyle p_{1}+2p_{2}$
Let $\displaystyle k=\frac{\Delta}{\delta}.$ We shall prove the following
inequality.

######  Claim 5.

$\displaystyle p_{1}+2p_{2}\leq(p_{3}+p_{4}+p_{5})(k-2)+\frac{2}{\delta}p_{2}$
where $\displaystyle p_{i}$ is the number of paths of order $\displaystyle i$
in $\displaystyle\mathcal{P}^{\prime}$.

###### Proof of Claim 5.

Put $\displaystyle p_{{}_{4}}^{\prime}=\left|\mathcal{R}_{4}^{1}\right|$ and
$\displaystyle p_{{}_{4}}^{\prime\prime}=\left|\mathcal{R}_{4}^{2}\right|.$
Let $\displaystyle\varepsilon\left(X,W\right)$ be the number of edges between
$\displaystyle X$ and $\displaystyle W$. Let $\displaystyle w$ be any vertex
of $\displaystyle W$. Observe that for $\displaystyle w\in$$\displaystyle
Int\left(\mathcal{R}_{5}\right)$, $\displaystyle w$ has at most
$\displaystyle\Delta-2$ neighbors in $\displaystyle X.$ For $\displaystyle
w\in Int\left(\mathcal{R}_{4}^{1}\right),$ then $\displaystyle w$ has at least
one neighbor which does not belong to $\displaystyle X$ and so, $\displaystyle
w$ has at most $\displaystyle\Delta-1$ neighbors in $\displaystyle X.$ By
Claim 3, if $\displaystyle w\in Int\left(\mathcal{R}_{4}^{2}\right),$ then
$\displaystyle w$ has exactly two neighbors in $\displaystyle X.$ If
$\displaystyle w\in$$\displaystyle W\cap Int{R}_{3}$ then $\displaystyle w$
has at most $\displaystyle\Delta$ neighbors in $\displaystyle X.$ It follows
that $\displaystyle\varepsilon\left(X,W\right)\leq
p_{3}\Delta+p_{4}^{\prime}\left(\Delta-1\right)+4p_{4}^{\prime\prime}+p_{5}\left(\Delta-2\right).$

On the other hand, by Claim 4,
$\displaystyle\varepsilon\left(X,W\right)\geq\sum\limits_{x\in
End(\mathcal{R}_{1})}d(x)+\sum\limits_{x\in
End(\mathcal{R}_{2})}(d(x)-1)+\sum\limits_{x\in End(\mathcal{R}_{3})\cap
X}d(x)$
$\displaystyle{+}$$\displaystyle\sum\limits_{x_{1},x_{2}\in
End(\mathcal{R}_{4}^{1})\cap
X}(d(x_{1})+d(x_{2})-1)+\sum\limits_{x_{1},x_{2}\in
End(\mathcal{R}_{4}^{2})\cap X}(d(x_{1})+d(x_{2}))$
$\displaystyle+\sum\limits_{x\in End(\mathcal{R}_{5})\cap X}(d(x)-1).$

As for each $\displaystyle x\in X$ we have $\displaystyle\delta\leq d(x)$, it
follows that
$\displaystyle
p_{{}_{1}}\delta+2p_{{}_{2}}(\delta-1)+2p_{{}_{3}}\delta+p_{{}_{4}}^{\prime}(2\delta-1)+p_{4}^{\prime\prime}2\delta+2p_{{}_{5}}(\delta-1)\leq
p_{3}\Delta+p_{4}^{\prime}\left(\Delta-1\right)+4p_{4}^{\prime\prime}+p_{5}\left(\Delta-2\right)$.
As $\displaystyle k\geq 2$ and $\displaystyle\delta$ $\displaystyle\geq 2,$
then $\displaystyle\Delta\geq 4$ and we replace $\displaystyle
4p_{4}^{\prime\prime}$ by $\displaystyle\Delta p_{4}^{\prime\prime}$ in the
last inequality. Then $\displaystyle
p_{{}_{1}}\delta+2p_{{}_{2}}(\delta-1)+2p_{{}_{3}}\delta+p_{{}_{4}}^{\prime}(2\delta-1)+p_{{}_{4}}^{\prime\prime}2\delta+2p_{{}_{5}}(\delta-1)\leq
p_{3}\Delta+p_{4}^{\prime}\left(\Delta-1\right)+p_{4}^{\prime\prime}\Delta$$\displaystyle+p_{5}\left(\Delta-2\right).$
As $\displaystyle p_{{}_{4}}=p_{{}_{4}}^{\prime}+p_{{}_{4}}^{\prime\prime}$,
we get $\displaystyle p_{{}_{1}}\delta+2p_{{}_{2}}(\delta-1)\leq
p_{3}\left(\Delta-2\delta\right)+p_{4}\left(\Delta-2\delta\right)+p_{5}\left(\Delta-2\delta\right).$
Since $\displaystyle\Delta=k\delta,$ then

$p_{1}+2p_{2}\leq(p_{3}+p_{4}+p_{5})(k-2)+\frac{2}{\delta}p_{2}.$

This completes the proof of Claim 5 ∎

2) Calculation of the bound of
$\displaystyle\left|\mathcal{P}^{\prime}\right|=p$
By Claim 5, there exists $\displaystyle r\leq k-2,$ such that

$p_{{}_{1}}+2p_{{}_{2}}=r\left(p_{{}_{3}}+p_{{}_{4}}+p_{{}_{5}}\right)+\frac{2}{\delta}p_{{}_{2}}$
(3)

Let us call $\displaystyle n_{1}$ the order of $\displaystyle
V(\mathcal{P}^{\prime})$. Clearly

$p=p_{{}_{1}}+p_{{}_{2}}+p_{{}_{3}}+p_{{}_{4}}+p_{{}_{5}}$

and

$n_{1}=p_{{}_{1}}+2p_{{}_{2}}+3p_{{}_{3}}+4p_{{}_{4}}+5p_{{}_{5}}.$

Using equality (3), we obtain

$p=\left(r+1\right)\left(p_{{}_{3}}+p_{{}_{4}}+p_{{}_{5}}\right)+\left(\frac{2}{\delta}-1\right)p_{{}_{2}}.$

As $\displaystyle\delta\geq 2,$ we get $\displaystyle
p\leq\left(r+1\right)\left(p_{{}_{3}}+p_{{}_{4}}+p_{{}_{5}}\right).$ Again by
equality (3), we have
$\displaystyle
n_{1}=\left(r+3\right)p_{{}_{3}}+\left(r+4\right)p_{{}_{4}}+\left(r+5\right)p_{{}_{5}}+\frac{2}{\delta}p_{{}_{2}}.$
This yields

$n_{1}\geq\left(r+3\right)(p_{{}_{3}}+p_{{}_{4}}+p_{{}_{5}}).$

Since $\displaystyle r\leq\left(k-2\right),$ we get the inequality
$\displaystyle p\leq\frac{k-1}{k+1}n_{1}.$
3) Bound of $\displaystyle\mu(G)$
Let $\displaystyle G_{2}=G-V(\mathcal{P}^{\prime}).$ Let $\displaystyle
n_{2}=n-n_{1}.$ Clearly $\displaystyle\mu(G)\leq p+\mu(G_{2}).$ We know that
$\displaystyle p\leq\frac{k-1}{k+1}n_{1}.$ Recall that each path of
$\displaystyle\mathcal{P}_{0}$ contained in $\displaystyle G_{2}$ has order at
least $\displaystyle 3$. It follows that
$\displaystyle\mu(G_{2})\leq\frac{n_{2}}{3}.$ Since $\displaystyle k\geq 2,$
we have $\displaystyle\frac{1}{3}\leq\frac{k-1}{k+1}$ and so
$\displaystyle\mu(G_{2})\leq\frac{k-1}{k+1}n_{2}.$ Thus
$\displaystyle\mu(G)\leq\frac{k-1}{k+1}n.$ This finishes the proof of the
theorem.$\displaystyle\blacksquare$

## References

## References

  * [1] M. Chen, J. Li, L. Wang and L. Zhang, On partitioning simple bipartite graphs in vertex-disjoint paths, Southeast Asian Bull. Math. $\displaystyle 31$ $\displaystyle(2)$ $\displaystyle(2007)$, $\displaystyle 225$–$\displaystyle 230$.
  * [2] H. Enomoto and K. Ota, Partitions of a graph into paths with prescribed endvertices and lengths, J. Graph Theory $\displaystyle 34$ $\displaystyle(2)$ $\displaystyle(2000)$, $\displaystyle 163$-$\displaystyle 169$.
  * [3] V. Gruslys and S. Letzter, Cycle partitions of regular graphs, arXiv: $\displaystyle 1808$.[math. CO]$\displaystyle 2$ Aug $\displaystyle 2018$.
  * [4] Jie Han, On vertex-disjoint paths in regular graphs, Electronic Journal of Combinatorics $\displaystyle 25$($\displaystyle 2$) ($\displaystyle 2018$), #$\displaystyle P2$.$\displaystyle 12.$
  * [5] R. Johansson, An El-Zahar type condition ensuring path-factors, J. Graph Theory $\displaystyle 28$ $\displaystyle(1)$ $\displaystyle(1998)$, $\displaystyle 39$–$\displaystyle 42$.
  * [6] M. Kouider, Neighborhoods and covering vertices by cycles, Combinatorica $\displaystyle 20$ ($\displaystyle 2$) ($\displaystyle 2000$) $\displaystyle 219$–$\displaystyle 226.$
  * [7] M. Kouider, Covering vertices by cycles, J. Graph Theory $\displaystyle 18$, $\displaystyle 757$–$\displaystyle 776$.
  * [8] M. Kouider and Z. Lonc, Covering cycles and $\displaystyle k$-term degree sums, Combinatorica $\displaystyle 16$ ($\displaystyle 1996$), $\displaystyle 407$–$\displaystyle 412$.
  * [9] J. Li and G. Steiner, Partitioning a bipartite graph into vertex-disjoint paths, Ars Combin. $\displaystyle 81$ $\displaystyle(2006)$, $\displaystyle 161$–$\displaystyle 173$.
  * [10] Ch. Lu and Qing Zhou, Path covering number and L($\displaystyle 2$, $\displaystyle 1$)-labeling number of graphs, arXiv:$\displaystyle 1204.2306v1$ [math.CO] $\displaystyle 10$ Apr $\displaystyle 2012$.
  * [11] C. Magnant and D.M. Martin, A note on the path cover number of regular graphs, Australasian Journal Of Combinatorics. $\displaystyle 43$ $\displaystyle\left(2009\right),$ $\displaystyle 211$-$\displaystyle 217$.
  * [12] C. Magnant and H. Wang, Path partition of almost regular graphs, Australasian Journal Of Combinatorics. $\displaystyle 64$ $\displaystyle\left(2016\right),$ $\displaystyle 334$-$\displaystyle 340$.
  * [13] P. Manuel, Revisiting path-type covering and partitioning problems, Hal-$\displaystyle 01849313$.
  * [14] O. Ore, Arc coverings of graphs, Ann. Mat. Pura Appl. $\displaystyle 55$ ($\displaystyle 4$) ($\displaystyle 1961$), $\displaystyle 315$–$\displaystyle 321$.
  * [15] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. $\displaystyle 5$ $\displaystyle(3)$ $\displaystyle(1996)$, $\displaystyle 277$–$\displaystyle 295$.
  * [16] G. Yu, A proof of Reed’s Conjecture on path cover of $\displaystyle 3$-regular graphs, (to appear).

Declaration

The authors declare no funds no grants were received during the preparation of
the manuscript
The authors declare they have no interest to disclose.
All the authors contribuated to this work and they approve the final
manuscript.