Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.03933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911882952048640 |
|---|---|
| author | Boyer, Geoffrey Goddard, Wayne |
| author_facet | Boyer, Geoffrey Goddard, Wayne |
| contents | An isolating set in a graph is a set $X$ of vertices such that every edge of the graph is incident with a vertex of $X$ or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least $6$. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03933 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Disjoint Isolating Sets and Graphs with Maximum Isolation Number Boyer, Geoffrey Goddard, Wayne Combinatorics 05C69 An isolating set in a graph is a set $X$ of vertices such that every edge of the graph is incident with a vertex of $X$ or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least $6$. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. |
| title | Disjoint Isolating Sets and Graphs with Maximum Isolation Number |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2401.03933 |