The enclaveless competition game

Michael A. Henning, Douglas F. Rall


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 [J. Res. Nat. Bur. Standards 82 (1977), 197–202], 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 [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 |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.


Competition-enclaveless game, domination game

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications