Premium
An upper bound for the path number of a graph
Author(s) -
Donald Alan
Publication year - 1980
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190040207
Subject(s) - combinatorics , mathematics , path graph , bound graph , graph , disjoint sets , upper and lower bounds , path (computing) , wheel graph , discrete mathematics , graph power , line graph , computer science , mathematical analysis , programming language
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/4 g ] ≤ [3/4 n ].