Distance matrix of a graph and its realizability

Abstract

The distances in a linear graph are described by a distance matrix . The realizability of a given by a linear graph is discussed and conditions under which the realization of is unique are established. The optimum realization of , (i.e., the realization of with ``minimum total length"), is investigated. A procedure is given by which a tree realization of can be found, if such a realization exists. Finally, it is shown that a tree realization, if it exists, is unique and is the optimum realization of .