Name
Abstract | ||
|---|---|---|
Timber is a two player game played on a directed graph, with a domino on each arc. The direction of an arc indicates the direction its domino can be toppled. Once a domino is toppled, it creates a chain reaction toppling all dominoes along that direction, and the player who topples the last domino wins. A P-position is an orientation of the edges of the graph where the second player can always force a win. A connected graph with a cycle has no P-position, thus Timber is a game studied in trees. We prove that a tree has a P-position if and only if the number of edges is even, which generalizes the existing characterization for paths and improves the performance of the existing algorithm to decide if an oriented tree with an odd number of arcs is a P-position. We contribute to the open problem of determining the number of P-positions of a tree. We compute the number of P-positions of three caterpillar infinite subclasses. Finally, we present a lower bound to the number of P-positions of an arbitrary caterpillar. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2017.11.011 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph theory,Combinatorial games,Impartial games,Digraph,Timber game,Caterpillar | Two-player game,Discrete mathematics,Combinatorics,Arc (geometry),Open problem,Upper and lower bounds,Directed graph,Domino,Counting problem,Connectivity,Mathematics | Journal |
Volume | ISSN | Citations |
261 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ana Maria Furtado | 1 | 0 | 0.34 |
| Simone Dantas | 2 | 119 | 24.99 |
| Celina M. H. de Figueiredo | 3 | 296 | 38.49 |
| Sylvain Gravier | 4 | 486 | 59.01 |