The enclaveless competition game

DOI10.26493/1855-3974.2227.E1AMaRDI QIDQ5156013zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Douglas F. Rall

Publication date 14 October 2021

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.02829

zbMATH Keywords

competition-enclaveless gamedomination game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 2-person games (91A05) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: For a subset $S$ of vertices in a graph $G$, a vertex $vinS$ 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 $Psi(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 $gamma(G)+Psi(G)=n$ where $gamma(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 Phillips 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 $Ps{i}_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 $Ps{i}_g^{+}(G)gefrac12n$. We prove this conjecture for regular graphs and for claw-free graphs.

Recommendations

• scientific article; zbMATH DE number 1933246
• The competition-independence game in trees
• scientific article; zbMATH DE number 2170474
• Extremal problems for game domination number
• On the game total domination number

Cites work

• Competition parameters of a graph
• Domination game and an imagination strategy
• Domination game on forests
• Domination game on paths and cycles
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Domination game: extremal families for the 3/5-conjecture for forests
• Domination games played on graphs
• Edge weighting functions on dominating sets
• Enclaveless sets and MK-Systems
• Extremal problems for game domination number
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 1933246 (Why is no real title available?)
• Independence and upper irredundance in claw-free graphs
• My favorite domination game conjectures
• On the game domination number of graphs with given minimum degree
• Properties of Hereditary Hypergraphs and Middle Graphs
• Realizations of the game domination number
• The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests
• The competition-independence game in trees

Cited in

(3)

• scientific article; zbMATH DE number 1933246 (Why is no real title available?)
• scientific article; zbMATH DE number 2170474 (Why is no real title available?)
• Optimal strategies in fractional games: vertex cover and domination

This page was built for publication: The enclaveless competition game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5156013)