Families of $2$-weights of some particular graphs

Abstract

Let $\mathcal{G}=(G,w)$ be a positive-weighted graph, that is a graph $G$ endowed with a function $w$ from the edge set of $G$ to the set of positive real numbers; for any distinct vertices $i,j$, we define $D_{i,j}(\mathcal{G})$ to be the weight of the path in $G$ joining $i$ and $j$ with minimum weight. In this paper we fix a particular class of graphs and we give a criterion to establish whether, given a family of positive real numbers $\{D_I{\}}_{I\in \left(\genfrac{}{}{0ex}{}{\{1,....,n\}}{2}\right)}$, there exists a positive-weighted graph $\mathcal{G}=(G,w)$ in the class we have fixed, with vertex set equal to $\{1,....,n\}$ and such that $D_I(\mathcal{G})=D_I$ for any $I\in \left(\genfrac{}{}{0ex}{}{\{1,....,n\}}{2}\right)$. In particular, the classes of graphs we consider are the following: snakes, caterpillars, polygons, bipartite graphs, complete graphs, planar graphs.

14 pages

References in corpus (1)

• Recognizing Treelike k-Dissimilarities