On the weights of simple paths in weighted complete graphs

DOI10.1007/S13226-013-0027-6MaRDI QIDQ384869zbMATH OpenOpenAlexFDO

Authors Elena Rubei

Publication date 29 November 2013

Published in Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0845

zbMATH Keywords

weights of graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22)

Abstract: Consider a weighted graph G with n vertices, numbered by the set {1,...,n}. For any path p in G, we call w_G(p) the sum of the weights of the edges of the path and we define the multiset {cal D}_{i,j} (G) = {w_G(p) | p simple path between i and j} We establish a criterion to say when, given a multisubset of the set of the real numbers there exists a weighted complete graph G such that the multisubset is equal to {cal D}_{i,j} (G) for some i,j vertices of G. Besides we establish a criterion to say when, given for any i, j in {1,...,n} a multisubset of the set of the real numbers,{cal D}_{i,j}, there exists a weighted complete graph G with vertices {1,...,n} such that {cal D}_{i,j} (G)= {cal D}_{i,j} for any i,j.

Recommendations

• Note on weights of paths in polyhedral graphs
• Heavy paths and cycles in weighted graphs
• scientific article; zbMATH DE number 10422
• Path covers of weighted graphs
• On the \(k\)-simple shortest paths problem in weighted directed graphs
• On the k Shortest Simple Paths Problem in Weighted Directed Graphs
• Path ideals of weighted graphs
• On the enumeration of certain weighted graphs
• scientific article; zbMATH DE number 1958431

Cites work

• A note on the metric properties of trees
• A note on the tree realizability of a distance matrix
• Basic phylogenetic combinatorics.
• Distance matrix of a graph and its realizability
• Hereditarily optimal realizations of consistent metrics
• On dissimilarity vectors of general weighted trees
• On graphlike \(k\)-dissimilarity vectors
• Recognizing treelike \(k\)-dissimilarities
• Reconstructing trees from subtree weights.
• Sets of double and triple weights of trees
• Symmetric Matrices Representable by Weighted Trees over a Cancellative Abelian Monoid
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers

Cited in

(2)

• Note on weights of paths in polyhedral graphs
• Weighted graphs with distances in given ranges

This page was built for publication: On the weights of simple paths in weighted complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q384869)