Results on three problems on isolation of graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908854120349696 |
|---|---|
| author | Borg, Peter Caro, Yair |
| author_facet | Borg, Peter Caro, Yair |
| contents | 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 $ι(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 $ι(G,F)$ with $d$ sufficiently large. We also investigate how close $ι(G,tF)$ is to $ι(G,F)$, using domination and, in suitable cases, the Erdos-Posa property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22856 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Results on three problems on isolation of graphs Borg, Peter Caro, Yair Combinatorics Computational Complexity Discrete Mathematics 05C35, 05C69, 03D15, 68Q17 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 $ι(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 $ι(G,F)$ with $d$ sufficiently large. We also investigate how close $ι(G,tF)$ is to $ι(G,F)$, using domination and, in suitable cases, the Erdos-Posa property. |
| title | Results on three problems on isolation of graphs |
| topic | Combinatorics Computational Complexity Discrete Mathematics 05C35, 05C69, 03D15, 68Q17 |
| url | https://arxiv.org/abs/2602.22856 |