Path Covering Number
The path covering number (or path-covering number; Slater 1972) of a graph G, variously denoted as summarized below, is the minimum number of vertex-disjoint paths that cover the vertices of G.
In order for the path covering number to be well-defined (for example, in the case of the claw graph K_(1,3), 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 alpha is the independence number,
| alpha>=rho, |
with equality for only complete graphs (DeLa Vina and Waller 2002).
See also
Graph PathExplore with Wolfram|Alpha
More things to try:
References
Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.Goedgebeur, J.; Ozeki, K.; van Cleemput, N.; and Wiener, G. "On the Minimum Leaf Number of Cubic Graphs." Disc. Math. 342, 3000-3005, 2019.Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.Lu, C. and Zhou, Q. "Path Covering Number and L(2,1)-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.Referenced on Wolfram|Alpha
Path Covering NumberCite this as:
Weisstein, Eric W. "Path Covering Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PathCoveringNumber.html