On the isolation number of graphs with minimum degree four
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911130054557696 |
|---|---|
| author | Goddard, Wayne Henning, Michael A. |
| author_facet | Goddard, Wayne Henning, Michael A. |
| contents | An isolating set in a graph $G$ is a set $S$ of vertices such that removing $S$ and its neighborhood leaves no edge. The isolation number $ι(G)$ of $G$ (also known as the vertex-edge domination number) is the minimum size among all isolating sets of $G$. We provide a technique for proving upper bounds on this parameter for graphs with a given minimum degree. For example, we show that if $G$ has order~$n$ and minimum degree at least~$4$, then $ι(G) \le 13n/41$, and if $G$ is also triangle-free, then $ι(G) \le 3n/10$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21551 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the isolation number of graphs with minimum degree four Goddard, Wayne Henning, Michael A. Combinatorics 05c69 An isolating set in a graph $G$ is a set $S$ of vertices such that removing $S$ and its neighborhood leaves no edge. The isolation number $ι(G)$ of $G$ (also known as the vertex-edge domination number) is the minimum size among all isolating sets of $G$. We provide a technique for proving upper bounds on this parameter for graphs with a given minimum degree. For example, we show that if $G$ has order~$n$ and minimum degree at least~$4$, then $ι(G) \le 13n/41$, and if $G$ is also triangle-free, then $ι(G) \le 3n/10$. |
| title | On the isolation number of graphs with minimum degree four |
| topic | Combinatorics 05c69 |
| url | https://arxiv.org/abs/2508.21551 |