We study the set of lower bounds which have been proposed for the numbering of a complete graph. We first show that the computation of most of them can be reformulated as a flow circulation problem with only positive components except for one. This leads to the definition of a family of lower bounds, and we discuss how to find the best possible member of it. Numerical values of the best possible lower bound are provided for graphs with up to 23 vertices and compared with their optimal numbers.
Published March 1997 , 32 pages
This cahier was revised in August 1997