Chip-firing games on mutating graphs

被引：13

作者：

Eriksson, K

机构：

[1] Department of Mathematics, Royal Institute of Technology

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1996年 / 9卷 / 01期

关键词：

chip firing; eulerian graph; period length; game length;

D O I：

10.1137/S0895480192240287

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate a generalization of a chip-firing game on a graph of Bjorner, Lovasz, and Shor [European J. Combin., 1 (1992), pp. 305-328]. In our version, the graph mutates during play. We show that some known results about the game length and period length of the earlier game hold for the mutating version as well, and some completely new bounds are also obtained. In a small detour, we treat an orientability concept for eulerian graphs.

引用

页码：118 / 128

页数：11

共 26 条

[1] Chip-firing games, potential theory on graphs, and spanning trees
Baker, Matthew
Shokrieh, Farbod
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (01) : 164 - 182
[2] Chip-firing and rotor-routing on directed graphs
Holroyd, Alexander E.
Levine, Lionel
Meszaros, Karola
Peres, Yuval
Propp, James
Wilson, David B.
IN AND OUT OF EQUILIBRIUM 2, 2008, 60 : 331 - +
[3] A constant bound for the periods of parallel chip-firing games with many chips
Paul Myer Kominers
Scott Duke Kominers
Archiv der Mathematik, 2010, 95 : 9 - 13
[4] A constant bound for the periods of parallel chip-firing games with many chips
Kominers, Paul Myer
Kominers, Scott Duke
ARCHIV DER MATHEMATIK, 2010, 95 (01) : 9 - 13
[5] A greedy chip-firing game
Li, Rupert
Propp, James
RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (03) : 645 - 666
[6] Confluence in labeled chip-firing
Klivans, Caroline
Liscio, Patrick
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2022, 186
[7] Sorting via chip-firing
Hopkins, Sam
McConville, Thomas
Propp, James
ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (03)
[8] Chip-Firing and the Critical Group of a Graph
N.L. Biggs
Journal of Algebraic Combinatorics, 1999, 9 : 25 - 45
[9] Chip-firing groups of iterated cones
Brown, Morgan V.
Morrow, Jackson S.
Zureick-Brown, David
LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 556 : 46 - 54
[10] Chip-firing and the critical group of a graph
Biggs, NL
JOURNAL OF ALGEBRAIC COMBINATORICS, 1999, 9 (01) : 25 - 45

← 1 2 3 →