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

Original language | English |
---|---|

Pages (from-to) | 129-142 |

Number of pages | 14 |

Journal | Ars Mathematica Contemporanea |

Volume | 20 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2021 |

## Keywords

- Competition-enclaveless game
- Domination game

## ASJC Scopus subject areas

- Theoretical Computer Science
- Algebra and Number Theory
- Geometry and Topology
- Discrete Mathematics and Combinatorics