BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Paul Dorbec appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
The game domination number is a graph invariant that arises from a game, which is related to graph domination in a similar way as the game chromatic number is related to graph coloring. In this paper we show that verifying whether the game domination number of a graph is bounded by a given integer is PSPACE-complete. This contrasts the situation of the game coloring problem whose complexity is still unknown.
In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for $γ\_{p,k}(G-e)$, $γ\_{p,k}(G/e)$ and for $γ\_{p,k}(G-v)$ in terms of $γ\_{p,k}(G)$, and give examples for which these bounds are tight. We characterize all graphs for which $γ\_{p,k}(G-e) = γ\_{p,k}(G)+1$ for any edge $e$. We also consider the behaviour of the propagation radius of graphs by similar modifications.
This paper deals with sliding games, which are a variant of the better known pushpush game. On a given structure (grid, torus...), a robot can move in a specific set of directions, and stops when it hits a block or boundary of the structure. The objective is to place the minimum number of blocks such that the robot can visit all the possible positions of the structure. In particular, we give the exact value of this number when playing on a rectangular grid and a torus. Other variants of this game are also considered, by constraining the robot to stop on each case, or by replacing blocks by walls.
The domination game is played on a graph $G$ by two players, named Dominator and Staller. They alternatively select vertices of $G$ such that each chosen vertex enlarges the set of vertices dominated before the move on it. Dominator's goal is that the game is finished as soon as possible, while Staller wants the game to last as long as possible. It is assumed that both play optimally. Game 1 and Game 2 are variants of the game in which Dominator and Staller has the first move, respectively. The game domination number $γ_g(G)$, and the Staller-start game domination number $γ_g'(G)$, is the number of vertices chosen in Game 1 and Game 2, respectively. It is proved that if $e\in E(G)$, then $|γ_g(G) - γ_g(G-e)| \le 2$ and $|γ_g'(G) - γ_g'(G-e)| \le 2$, and that each of the possibilities here is realizable by connected graphs $G$ for all values of $γ_g(G)$ and $γ_g'(G)$ larger than 5. For the remaining small values it is either proved that realizations are not possible or realizing examples are provided. It is also proved that if $v\in V(G)$, then $γ_g(G) - γ_g(G-v) \le 2$ and $γ_g'(G) - γ_g'(G-v) \le 2$. Possibilities here are again realizable by connected graphs $G$ in almost all the cases, the exceptional values are treated similarly as in the edge-removal case.