Distance matrix of a graph and its realizability

Abstract

The distances in a linear graph are described by a distance matrix <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The realizability of a given <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> by a linear graph is discussed and conditions under which the realization of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is unique are established. The optimum realization of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, (i.e., the realization of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with “minimum total length"), is investigated. A procedure is given by which a tree realization of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.