Journal of Combinatorics
Volume 3 (2012)
Chipping away at the edges: How long does it take?
Pages: 101 – 121
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.
single-node traffic flow process, graph searching, chip-firing game
2010 Mathematics Subject Classification
05C50, 05C57, 05C78, 05C85