The path covering number (or path-covering number; Slater 1972) of a graph 
, variously denoted as summarized below,
is the minimum number of vertex-disjoint paths
that cover the vertices of 
.
| notation | reference |
 | Boesch et al. (1974) |
 | Slater (1979) |
 | DeLa Vina and Waller (2002) |
 | Goedgebeur et al. (2019) |
 | Lu and Zhou (2013) |
In order for the path covering number to be well-defined (for example, in the case of the claw graph 
, for which one or two vertices
are "left over" after covering with paths
of length 2 or 1, respectively), "paths"
consisting of a single point must be allowed (Boesch et
al. 1974).
A graph therefore has path covering number 1 iff it is traceable (Boesch et al. 1974).
A disconnected graph has a path covering number equal to the sum of the path covering numbers of its connected components.
Boesch et al. (1974) give values for a number of parametrized classes of graphs.
Lovasz (1979, p. 55) showed that when 
is the independence
number,
 |
Equality holds for complete graphs (DeLa Vina and Waller 2002).
-Labeling
Number of Graphs." Disc. Appl. Math. 161, 2062-2074, 2013.Ore,
Ø. "Arc Coverings of Graphs." Ann. Mat. Pura Appl. 55,
315-332, 1961.Slater, P. J. "Path Coverings of the Vertices
of a Tree." Disc. Math. 25, 65-74, 1979.