Graph odometry

DOI10.1016/J.DAM.2016.06.023MaRDI QIDQ317413zbMATH OpenOpenAlexFDO

Authors Bill Kay, Aaron Dutle

Publication date 30 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph reconstructionMenger's theoremnon-backtracking walk

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Abstract: We address problem of determining edge weights on a graph using non-backtracking closed walks from a vertex. We show that the weights of all of the edges can be determined from any starting vertex exactly when the graph has minimum degree at least three. We also determine the minimum number of walks required to reveal all edge weights.

Recommendations

• On a max-min problem concerning weights of edges
• scientific article; zbMATH DE number 125461
• scientific article; zbMATH DE number 426346
• Edge weights and vertex colours
• Bounded degree graph inference from walks

Cites work

• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3458693 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Combinatorial Aspects of the Ising Model for Ferromagnetism. I. A Conjecture of Feynman on Paths and Graphs
• Combinatorics of Train Tracks. (AM-125)

This page was built for publication: Graph odometry

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