Chipping away at the edges: How long does it take?

We introduce the single-node traffic flow process, which is related to both the chip-firing game and the edge searching process. Initially, real-valued weights (instead of chips) are placed on some vertices, and all the edges have zero weight. When a vertex is “fired”, the whole content accumulated in this vertex is sent uniformly to all its neighbours, and each edge increases its weight by the amount that is sent through this edge. We would like to discover the shortest firing sequence such that the total amount of traffic that has passed through each edge is at least some fixed value. A complete characterization for complete graphs is presented as well as discussion of other classes of graphs.

Keywords

single-node traffic flow process, graph searching, chip-firing game

2010 Mathematics Subject Classification

05C50, 05C57, 05C78, 05C85

Full Text (PDF format)

Published 11 September 2012