The structure of distances in networks

✍ Scribed by Eric Howe; Charles R. Johnson; James Lawrence

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 891 KB
• Volume: 16
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230160109

✦ Synopsis

Part of this work is concerned with determining those graphs that produce extreme rays of the cone of shortest distance matrices of undirected linear ti-vertex graphs without loops. For n 5 4, for example, all extreme rays come from a certain class of "+mentary" graphs. but for n 2 5 there are nonelementary extreme rays. and these are studied further. Another part of this work is concerned with the representation of a distance matrix as a set of distances among points in a normed vector space. The set of graphs (distance matrices) representable by a given norm and the set of norms (and dimensions of spaces) by which a given graph may be represented are studied. It is shown that I, is unique among 1, norms in that any graph is I, representable in R" I. The 1, representable distance matrices are found to be just those in the cone generated by elementaries for all n. Other results on distance matrices are also included.

DEDICATION

We dedicate this paper to the memory of E. K . McLachlan.