The enclaveless competition game - Henning, Michael A. (Ars mathematica contemporanea, 2021)
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 ?$Ψ(G)$? of ?$G$? is the maximum cardinality of an enclaveless set in ?$G$?. As first observed in P. J. Slate, J. Res. Natl. Bur. Stand. 82, 197-202 (1977), if $G$ is a graph with ?$n$? vertices, then ?$γ(G) + Ψ(G) = n$? where ?$γ(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 J. B. Philips and P. J. Slater "An introduction to graph competition independence and enclaveless parameters", Graph Theory Notes N. Y. 41, 37-41 (2001) and defined as follows. Two players take turns in constructing a maximal enclaveless set ?$S$?, where one player, Maximizer, tries to maximize ?$|S|$? and one player, Minimizer, tries to minimize ?$|S|$?. The competition-enclaveless game number ?$Ψ_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 ?$Ψ_g^+(G) ≥ \frac{1}{2} n$?. We prove this conjecture for regular graphs and for claw-free graphs.
Keywords: competition-enclaveless gam; dominacijska igra; domination game; tekmovalna brezenklavna igra