No polynomial bound for the chip firing game on directed graphs. (English) Zbl 0758.05060

The chips game for general graphs was formulated by A. Björner, L. Lovász and P. W. Shor [Eur. J. Comb. 12, No. 4, 283-291 (1991; Zbl 0729.05048)]. For undirected graphs, G. Tardos [SIAM J. Discrete Math. 1, No. 3, 397-398 (1988; Zbl 0652.68089)] gave an upper limit, \(O(n^ 4)\), on the number of moves in a game for which the number of nodes is bounded by \(n\). In this note we prove that for directed graphs no polynomial bound on the number of moves exists. In fact, we give an example of a sequence of games with exponential growth.


05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI


[1] A. Björner, L. Lovász, and P. Shor, Chip-firing games on graphs, preprint, 1987. · Zbl 0729.05048
[2] Gábor Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math. 1 (1988), no. 3, 397 – 398. · Zbl 0652.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.