Distance matrices of some positive-weighted graphs

Let {cal G}=(G,w) be a positive-weighted connected graph, that is a connected graph G endowed with a function w from the edge set of G to the set of positive real numbers, and let {1,...,n} be its vertex set; for any subgraph H of G, we define the weight of H to be the sum of the weights of the edges of H and, for any i,j in {1,...,n}, we define D_{i,j}({cal G}) to be the minimum weight of any path in G with endpoints i and j. Obviously the D_{i,j}({cal G}) form a symmetric n x n matrix with zero diagonal entries and positive off-diagonal entries. It is well-known that a symmetric matrix with zero diagonal entries and positive off-diagonal entries comes from a positive-weighted connected graph if and only if its entries satisfy the triangle inequalities. In this paper we consider some particular classes of graphs: paths, caterpillars, cycles, bipartite graphs, complete graphs, planar graphs; for each of these classes, we give a criterion to establish whether, given a symmetric n x n matrix D with zero diagonal entries and positive off-diagonal entries, there exists a positive-weighted graph {cal G} =(G,w) in the class we have fixed, with vertex set equal to {1,...,n} and such that D_{i,j} ({cal G}) =D_{i,j} for every i,j in {1,...,n}.