Geodesic
The enclaveless competition game
Ars Mathematica Contemporanea, Tome 20 (2021) no. 1, pp. 129-142.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2227.e1a
Keywords: Competition-enclaveless game, domination game 
@article{10_26493_1855_3974_2227_e1a,
     author = {Michael A. Henning and Douglas F. Rall},
     title = {The enclaveless competition game},
     journal = {Ars Mathematica Contemporanea},
     pages = {129--142},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2021},
     doi = {10.26493/1855-3974.2227.e1a},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2227.e1a/}
}
TY  - JOUR
AU  - Michael A. Henning
AU  - Douglas F. Rall
TI  - The enclaveless competition game
JO  - Ars Mathematica Contemporanea
PY  - 2021
SP  - 129
EP  - 142
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2227.e1a/
DO  - 10.26493/1855-3974.2227.e1a
LA  - en
ID  - 10_26493_1855_3974_2227_e1a
ER  - 
%0 Journal Article
%A Michael A. Henning
%A Douglas F. Rall
%T The enclaveless competition game
%J Ars Mathematica Contemporanea
%D 2021
%P 129-142
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2227.e1a/
%R 10.26493/1855-3974.2227.e1a
%G en
%F 10_26493_1855_3974_2227_e1a
Michael A. Henning; Douglas F. Rall. The enclaveless competition game. Ars Mathematica Contemporanea, Tome 20 (2021) no. 1, pp. 129-142. doi : 10.26493/1855-3974.2227.e1a. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2227.e1a/

Cité par Sources :