An upper bound for the path number of a graph |
| |
Authors: | Alan Donald |
| |
Abstract: | The path number of a graph G, denoted p(G), is the minimum number of edge-disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g - 1 ≤ n - 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n]. |
| |
Keywords: | |
|
|