路径覆盖数

图 的路径覆盖数（或路径覆盖数；Slater 1972），以下总结了不同的表示法，是覆盖图 的顶点所需的最小数量的顶点不相交路径。

符号	参考文献
	Boesch et al. (1974)
	Slater (1979)
	DeLa Vina and Waller (2002)
	Goedgebeur et al. (2019)
	Lu and Zhou (2013)

为了使路径覆盖数被良好定义（例如，在 爪形图 的情况下，对于该图，在使用长度为 2 或 1 的路径覆盖后，会“剩下”一个或两个顶点），必须允许由单个点组成的“路径”（Boesch et al. 1974）。

因此，一个图的路径覆盖数为 1 当且仅当 它是 可迹的 (Boesch et al. 1974)。

一个非连通图的路径覆盖数等于其连通分量的路径覆盖数之和。

Boesch (et al. 1974) 给出了许多参数化图类的路径覆盖数值。

Lovasz (1979, p. 55) 表明，当 是独立数时，

等式仅对 完全图 成立 (DeLa Vina and Waller 2002)。