路徑覆蓋數

圖 的路徑覆蓋數（或路徑覆蓋數；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)。