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}.
Distance matrices of some positive-weighted graphs / Baldisserri, Agnese; Rubei, Elena. - In: THE AUSTRALASIAN JOURNAL OF COMBINATORICS. - ISSN 2202-3518. - ELETTRONICO. - 70:(2018), pp. 185-201.
Distance matrices of some positive-weighted graphs
Agnese Baldisserri;Elena Rubei
2018
Abstract
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}.File | Dimensione | Formato | |
---|---|---|---|
27-B-R-AUSTRALASIAN.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
168.12 kB
Formato
Adobe PDF
|
168.12 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.