We introduce a competitive two-player zero forcing game on a connected graph. Alice and Bob alternately seed white vertices or perform legal zero forces in their own colours, and each player seeks to minimise their own number of seeds. A force preservation rule prevents avoidable blocking of an opponent's established force. Because distinct continuations can be equally good for the player to move, optimal play is defined by a set-valued backward induction, and \(Z_g(G)\) is the minimum total number of seeds among the resulting optimal outcomes. We prove that \(Z_g(G)\geq Z(G)\), determine \(Z_g\) for paths, cycles, stars, complete graphs, and complete bipartite graphs, and characterise the graphs with \(Z_g(G)=2\) by an alternating two-chain forcing schedule. We also show that \(Z_g\) is not minor-monotone and that edge subdivision can either increase or decrease the parameter. Exact computation verifies \(Z_g(G)\leq2Z(G)\) through order nine.
Let $\mathcal{B}$ be the class consisting of the six-vertex bipartite graphs that possess a perfect matching and their complements. It is proved that every $\mathcal{B}$-free graph $G$ satisfies $\alpha(G)+\omega(G)\ge |V(G)|-1$. This establishes Conjecture 3.1 of Litjens, Polak and Sivaraman (B-Free Graphs Conjecture)...
Let $G=(V,E)$ be a finite loopless directed graph. Each directed two-step diamond identifies its two pairs of opposite edges, and the connected components of the resulting auxiliary graph on $E$ define a canonical partition $\Pi_{\mathrm{opp}}(G)$. We ask whether a finite relational certificate built from the blocks of...
A combinatorial game is a two-player game without hidden information or chance elements. The main object of combinatorial game theory is to determine the outcome (i.e., which player has a winning strategy) of a given position in combinatorial games. Nim is a well-known and fundamental ruleset in combinatorial game theo...
The {\it zero forcing number} of a graph $G$, $Z(G)$, is a well-studied parameter which arises from a color changing process and has strong connections to {\it minimum rank}, {\it critical ideals} and related invariants. In this work, we consider the complementary parameter $\mz(G) = |V(G)| - Z(G)$. This parameter is m...
Carlos A. Alfaro, Michael D. Barrus, S. G. Gómez-Galicia et al.· 0 citations
Hartnell and Rall recently introduced the domatic number game. Alice and Bob color the vertices of a graph from a palette [\(k\)], and Alice wins if every color class is a dominating set at the end of the game. The largest winning palette size is denoted by \(\mathop{\mathrm{dom}}\nolimits_{g}(G)\) when Alice moves fir...
The $d/4$ bound for some infinite graph families, such as the hypercube graph $Q_d$, grids and tori, is improved and it is shown that Breaker can secure a degree of one at every vertex in $Q_3$, then lifted to higher dimensions, where Breaker can guarantee a degree of at least $\lfloor d/3 \rfloor$.
Lajos Gyõrffy· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
