Symmetric Matrices Representable by Weighted Trees over a Cancellative Abelian Monoid
Authors:
- Hans-Jürgen BandeltHBHans-Jürgen Bandelt
- Michael Anthony SteelMSMichael Anthony Steel
- 1 November 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 8 (4) , 517-525
Abstract
The classical result that characterizes metrics induced by paths in a labeled tree having positive real edge weights is generalized to allow the edge weights to take values in any cancellative abelian monoid satisfying the additional requirement that $x + x = y + y$ implies $x = y$. This includes the case of arbitrary real-valued edge weights, which applies to distance-hereditary graphs, thus yielding (unique) weighted tree representations for the latter.
Keywords
This publication has 4 references indexed in Scilit:
- Recognition of Tree MetricsSIAM Journal on Discrete Mathematics, 1990
- Distance-hereditary graphsJournal of Combinatorial Theory, Series B, 1986
- On metric properties of certain clique graphsJournal of Combinatorial Theory, Series B, 1979
- A note on the metric properties of treesJournal of Combinatorial Theory, Series B, 1974