The Enclaveless Competition Game

For a subset $S$ of vertices in a graph $G$, a vertex $v\in S$ is an enclave of $S$ if $v$ and all of its neighbors are in $S$, where a neighbor of $v$ is a vertex adjacent to $v$. A set $S$ is enclaveless if it does not contain any enclaves. The enclaveless number $\mathrm{\Psi }(G)$ of $G$ is the maximum cardinality of an enclaveless set in $G$. As first observed in 1997 by Slater [J. Res. Nat. Bur. Standards 82 (1977), 197–202], if $G$ is a graph with $n$ vertices, then $\gamma (G)+\mathrm{\Psi }(G)=n$ where $\gamma (G)$ is the well-studied domination number of $G$. In this paper, we continue the study of the competition-enclaveless game introduced in 2001 by Phillips and Slater [Graph Theory Notes N. Y. 41 (2001), 37–41] and defined as follows. Two players take turns in constructing a maximal enclaveless set $S$, where one player, Maximizer, tries to maximize $\mathrm{\mid }S\mathrm{\mid }$ and one player, Minimizer, tries to minimize~$\mathrm{\mid }S\mathrm{\mid }$. The competition-enclaveless game number ${\mathrm{\Psi }}_g^{+}(G)$ of $G$ is the number of vertices played when Maximizer starts the game and both players play optimally. We study among other problems the conjecture that if $G$ is an isolate-free graph of order $n$, then ${\mathrm{\Psi }}_g^{+}(G)\ge \frac{1}{2}n$. We prove this conjecture for regular graphs and for claw-free graphs.