On the path number of a digraph


Dragan Mašulović




The vertex path number of a digraph is the minimum number of vertex disjoint paths in the digraph which partition the set of vertices of the digraph. The edge path number of a digraph is the minimum number of edge disjoint paths in the digraph which partition the set of edges of the digraph. We show that the vertex and edge path numbers of a digraph are closely related and that the vertex path number of a digraph equals the minimum vertex path number of a spanning tree of the digraph.