BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
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∈E(G), then ∣γg(G)−γg(G−e)∣≤2 and ∣γg′(G)−γg′(G−e)∣≤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∈V(G), then γg(G)−γg(G−v)≤2 and γg′(G)−γg′(G−v)≤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.
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.