Graphlike families of multiweights

Abstract

Let $\mathcal{G}=(G,w)$ be a weighted graph , that is, a graph $G$ endowed with a function $w$ from the edge set of $G$ to the set of real numbers; for any subset $S$ of the vertex set of $G$, we define $D_S(\mathcal{G})$ to be the minimum of the weights of the subgraphs of $G$ whose vertex set contains $S$; we call $D_S(\mathcal{G})$ a multiweight of $\mathcal{G}$. Let $X$ be a finite set and let $\{D_S{\}}_{S\subset X,♯S\ge 2}$ be a family of positive real numbers. We find necessary and sufficient conditions for the family to be the family of multiweights of a positive-weighted graph with vertex set $X$. Moreover we study the analogous problem for trees. Finally, we find a criterion to say if there exists a nonnegative-weighted tree $\mathcal{T}$ with leaf set $X$ and such that $D_S(\mathcal{T})=D_S$ for any $S\subset X$.

11 pages, minor changes

Cited by in corpus (1)

• A characterization of distance matrices of weighted cubic graphs and Peterson graphs