Graph odometry

DOI10.1016/J.DAM.2016.06.023zbMATH Open1346.05100arXiv1211.2151OpenAlexW2912786499MaRDI QIDQ317413FDOQ317413

Authors: Bill Kay, Aaron Dutle 

Publication date: 30 September 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorics of Train Tracks. (AM-125)
• Title not available (Why is that?)
• Combinatorial Aspects of the Ising Model for Ferromagnetism. I. A Conjecture of Feynman on Paths and Graphs

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)