Scholarlink

<p>In 1992, Bitar and Goles introduced the parallel chip-firing game on undirected graphs. Two years later, Prisner extended the game to directed graphs. While the properties of parallel chip-firing games on undirected graphs have been extensively studied, their analogs for parallel chip-firing games on directed graphs have been sporadic. In this paper, we prove the outstanding analogs of the core results of parallel chip-firing games on undirected graphs for those on directed graphs. We find the possible periods of a parallel chip-firing game on a directed simple cycle and introduce the method of Gauss–Jordan elimination on a Laplacian-like matrix to establish a lower bound on the maximum period of a parallel chip-firing game on an orientation of an undirected complete graph and an undirected complete bipartite graph. Finally, we expand the method of motors by Jiang, Scully, and Zhang to directed graphs to show that a binary string <i>s</i> can be the atomic firing sequence of a vertex in a parallel chip-firing game on a strongly connected directed graph if and only if <i>s</i> contains 1 or <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_760_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(s=0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Periods and Atomic Firing Sequences of Parallel Chip-Firing Games on Directed Graphs

  • 期刊论文

  • 发表日期：

    2025年5月13日

查看全文
  • David Ji,
  • Michael Li,
  • Daniel Wang

摘要

In 1992, Bitar and Goles introduced the parallel chip-firing game on undirected graphs. Two years later, Prisner extended the game to directed graphs. While the properties of parallel chip-firing games on undirected graphs have been extensively studied, their analogs for parallel chip-firing games on directed graphs have been sporadic. In this paper, we prove the outstanding analogs of the core results of parallel chip-firing games on undirected graphs for those on directed graphs. We find the possible periods of a parallel chip-firing game on a directed simple cycle and introduce the method of Gauss–Jordan elimination on a Laplacian-like matrix to establish a lower bound on the maximum period of a parallel chip-firing game on an orientation of an undirected complete graph and an undirected complete bipartite graph. Finally, we expand the method of motors by Jiang, Scully, and Zhang to directed graphs to show that a binary string s can be the atomic firing sequence of a vertex in a parallel chip-firing game on a strongly connected directed graph if and only if s contains 1 or \(s=0\) s = 0 .