BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Gašper Košmrlj contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph 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.
A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$. In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.
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.