Group for Research in Decision Analysis


On Lower Bounds for Numbered Complete Graphs

, , and

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.

, 32 pages

This cahier was revised in August 1997