### 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 [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.

#### Keywords

#### Full Text:

MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.2227.e1a

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