## Graph Odometry

- Sept. 26, 2012
- 3:30 p.m.
- LeConte 312

## Abstract

A delivery company sets up shop on a vertex $v$ of an edge-weighted graph $G$. Unluckily, the company truck is too large to make a U-turn (except at the company lot), so every trip made must be a *non-backtracking closed walk* from $v.$ After making each delivery, the driver records the distance traveled, i.e., the sum of the weights of the edges traveled, counted with multiplicity. What
conditions must our graph satisfy so that the weight of every edge can be determined? How many walks are needed? Does the location of the start vertex matter? We address these and other questions.