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) gives values for a number of parametrized classes of graphs.
Lovasz (1979, p. 55) showed that when 
is the independence
number,
 |
with equality for only 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.