Upper bounds on isolation parameters
| Autor: | Borg, Peter, Lemańska, Magdalena, Mora, Mercè, Souto-Salorio, María José |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $\mathcal{F}$ be a set of graphs. A set $D$ of vertices of a graph $G$ is $\mathcal{F}$-isolating if the graph obtained by removing from $G$ all the vertices in $D$ and their neighbors does not have a copy of a graph in $\mathcal{F}$ as a subgraph. The $\mathcal{F}$-isolation number of $G$, denoted by $\iota(G, \mathcal{F})$, is the size of a smallest $\mathcal{F}$-isolating set of $G$. We establish sharp upper bounds on the $\mathcal{F}$-isolation number of a tree in terms of the order and the number of leaves for the case where $\mathcal{F}$ consists of the star $K_{1,k}$ for some $k\geq 1$. Moreover, we characterize all trees attaining the bounds. Comment: 27 pages, 14 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|