I'm looking for references on the following problem:
Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$?
i.e., let $P$ be the answer to this problem. Then $P$ has the following properties:
each member $p$ of $P$ is a simple path (a chain)-- i.e., no cycles on $p$, and every node except the $2$ end nodes (they have the degree $1$ each) has degree $2$,
for any $p_1$ and $p_2$ in $P$, there does not exist a vertex $v$ where $v$ is on both $p_1$ and $p_2$,
there does not exist a vertex $v$ in $V$ where $v$ is not on a path $p$ that is $P$, i.e., the paths in $P$ cover the vertex set,
there is no other such set $P'$ satisfying $|P'|<|P|$.
TIA.
//==========================
EDIT:
The graph is directed in a specific case. I'm interested in both directed and undirected cases.
This is called a minimum path cover, optimal path cover, or path partition. The number of paths in a minimum path cover is the path covering number. This paper gives quite an extensive list of references on the problem:
http://arxiv.org/pdf/1204.2306.pdf