Results on three problems on isolation of graphs

Abstract

The graph isolation problem was introduced by Caro and Hansberg in 2015. It is a vast generalization of the classical graph domination problem and its study is expanding rapidly. In this paper, we address a number of questions that arise naturally. Let $F$ be a graph. We show that the $F$-isolating set problem is NP-complete if $F$ is connected. We investigate how the $F$-isolation number ${\hat{I}}^1(G,F)$ of a graph $G$ is affected by the minimum degree $d$ of $G$, establishing a bounded range, in terms of $d$ and the orders of $F$ and $G$, for the largest possible value of ${\hat{I}}^1(G,F)$ with $d$ sufficiently large. We also investigate how close ${\hat{I}}^1(G,tF)$ is to ${\hat{I}}^1(G,F)$, using domination and, in suitable cases, the Erdos-Posa property.

12 pages