Eriksson, Kimmo No polynomial bound for the chip firing game on directed graphs. (English) Zbl 0758.05060 Proc. Am. Math. Soc. 112, No. 4, 1203-1205 (1991). 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. Cited in 7 Documents MSC: 05C35 Extremal problems in graph theory 05C20 Directed graphs (digraphs), tournaments Keywords:bound; chip firing game; directed graphs Citations:Zbl 0729.05048; Zbl 0652.68089 PDF BibTeX XML Cite \textit{K. Eriksson}, Proc. Am. Math. Soc. 112, No. 4, 1203--1205 (1991; Zbl 0758.05060) Full Text: DOI References: [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.