Covering the edges of a connected graph by paths (Q1907117)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Covering the edges of a connected graph by paths |
scientific article |
Statements
Covering the edges of a connected graph by paths (English)
0 references
27 June 1996
0 references
An edge cover of a graph \(G\) by paths is a set of paths so that every edge of \(G\) lies in at least one path. The author proves that every graph \(G\) of order \(n\) can be edge-covered by \({n\over 2}+ O(n^{3/4})\) paths.
0 references
path decomposition
0 references
edge cover
0 references
path
0 references
