The enclaveless competition game

Abstract

For a subset S of vertices in a graph G, a vertex v ∈ 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 1997 by Slater, 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 Philips and Slater 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) ≥ (1/2)n. We prove this conjecture for regular graphs and for claw-free graphs.