✦ LIBER ✦

On a game in directed graphs

✍ Scribed by Alan J. Hoffman; Kate Jenkins; Tim Roughgarden

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 61 KB
Volume: 83
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00309-x

No coin nor oath required. For personal study only.

✦ Synopsis

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no "nice" characterization of mortal graphs exists).

📜 SIMILAR VOLUMES

Kernels in directed graphs: a poison gam

Kernels in directed graphs: a poison game

✍ P. Duchet; H. Meyniel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 282 KB

We consider a two player game on a progressively and locally finite directed graph and we prove that the first player wins if and only if the graph has a local kernel. The result is sharp. From it, we derive a short proof of a general version of the Galeana-Sanchez & Neuman-Lara Theorem that give a

Directed triangles in directed graphs

✍ M. de Graaf; A. Schrijver; P.D. Seymour 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 212 KB

de Graaf, M., A. Schrijver and P.D. Seymour, Directed triangles in directed graphs, Discrete Mathematics 110 (1992) 279-282. h on n vertices, each with indegree and outdegree at least n/t, contains a directed circuit of length at most

A Nim game played on graphs

✍ Masahiko Fukuyama 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 262 KB

We propose a new impartial game played by two players, which can be compared to the well-known Nim game (Winning Ways

Combinatorial games on a graph

✍ Claude Berge 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 365 KB

Survey of various problems about combinatorial games. ## O. Introduction A combinatorial game is the situation where two players, usually called A and B, play alternately by selecting an element in a finite set X according to fixed rules; the first player to achieve a certain configuration has wo

On antimagic directed graphs

✍ Dan Hefetz; Torsten Mütze; Justus Schwartz 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract An antimagic labeling of an undirected graph __G__ with __n__ vertices and __m__ edges is a bijection from the set of edges of __G__ to the integers {1, …, __m__} such that all __n__ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with th

On persistent directed graphs

✍ Jorgen Bang-Jensen; Tibor Jordán 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB