IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC