What question did this study set out to answer?

This work aims to analyze a game where two players build an isolating set in a graph, focusing on the resulting isolation number.

March 5, 2026Open Access

Isolation Game on Graphs

Key Points

This work aims to analyze a game where two players build an isolating set in a graph, focusing on the resulting isolation number.
Introduced a game framework with two opposing players: Dominator and Staller.
Defined an isolating set in terms of a family of graphs to explore graph invariants.
Proved the Continuation Principle and analyzed the impact of the starting player.
Established that the difference in isolation numbers when players alternate starting is at most 1.
Showed relationships between isolation numbers of different graph families, revealing potential inequalities.
Presented specific cases where the isolation game is evaluated using a single graph family.

Abstract

Abstract Given a graph G and a family of graphs F F, an F F -isolating set, as introduced by Caro and Hansberg, is any set S V (G) S ⊂ V (G) such that G - NS G - N S contains no member of F F as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an F F -isolating set in G. Following the domination games, Dominator (Staller) wants that the resulting F F -isolating set obtained at the end of the game, is as small (as big) as possible, which leads to the graph invariant called the game F F -isolation number, denoted g (G, F) ι g (G, F). We prove that the Continuation Principle holds in the F F -isolation game, and that the difference between the game F F -isolation numbers when either Dominator or Staller starts the game is at most 1. Considering two arbitrary families of graphs F F and F' F ′, we find relations between them that ensure g (G, {F}') g (G, {F}) ι g (G, F ′) ≤ ι g (G, F) for any graph G. A special focus is given on the isolation game, which takes place when F=\K₂\ <mml: math xmlns: mml="http

KI fragen

Bookmark

View Full Paper