Page 1

## Displaying 1 – 19 of 19

Showing per page

### Colouring game and generalized colouring game on graphs with cut-vertices

Discussiones Mathematicae Graph Theory

For k ≥ 2 we define a class of graphs 𝓗 ₖ = {G: every block of G has at most k vertices}. The class 𝓗 ₖ contains among other graphs forests, Husimi trees, line graphs of forests, cactus graphs. We consider the colouring game and the generalized colouring game on graphs from 𝓗 ₖ.

### Domination Game Critical Graphs

Discussiones Mathematicae Graph Theory

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game...

### Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Discussiones Mathematicae Graph Theory

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107]...

### Game colouring directed graphs.

The Electronic Journal of Combinatorics [electronic only]

### How Long Can One Bluff in the Domination Game?

Discussiones Mathematicae Graph Theory

The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs...

### Motion planning in cartesian product graphs

Discussiones Mathematicae Graph Theory

Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path...

### Mr. Paint and Mrs. Correct.

The Electronic Journal of Combinatorics [electronic only]

### Mr. Paint and Mrs. Correct go fractional.

The Electronic Journal of Combinatorics [electronic only]

### Note: The Smallest Nonevasive Graph Property

Discussiones Mathematicae Graph Theory

A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that...

### On a generalization of Meyniel's conjecture on the Cops and Robbers game.

The Electronic Journal of Combinatorics [electronic only]

Integers

### On the Chvàtal-Erdős triangle game.

The Electronic Journal of Combinatorics [electronic only]

### On-line Ramsey theory for bounded degree graphs.

The Electronic Journal of Combinatorics [electronic only]

### Recursive algorithm for parity games requires exponential time

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.

### Recursive algorithm for parity games requires exponential time

RAIRO - Theoretical Informatics and Applications

This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.

### Signed Chip Firing Games and symmetric Sandpile Models on the cycles

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.

### The first player wins the one-colour triangle avoidance game on 16 vertices

Discussiones Mathematicae Graph Theory

We consider the one-colour triangle avoidance game. Using a high performance computing network, we showed that the first player can win the game on 16 vertices.

### The $t$-pebbling number is eventually linear in $t$.

The Electronic Journal of Combinatorics [electronic only]

### Winning strong games through fast strategies for weak games.

The Electronic Journal of Combinatorics [electronic only]

Page 1