Isolation partitions in graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909379004989440 |
|---|---|
| author | Zhang, Gang Yang, Weiling Jin, Xian'an |
| author_facet | Zhang, Gang Yang, Weiling Jin, Xian'an |
| contents | Let $G$ be a graph and $k \geq 3$ an integer. A subset $D \subseteq V(G)$ is a $k$-clique (resp., cycle) isolating set of $G$ if $G-N[D]$ contains no $k$-clique (resp., cycle). In this paper, we prove that every connected graph with maximum degree at most $k$, except $k$-clique, can be partitioned into $k+1$ disjoint $k$-clique isolating sets, and that every connected claw-free subcubic graph, except 3-cycle, can be partitioned into four disjoint cycle isolating sets. As a consequence of the first result, every $k$-regular graph can be partitioned into $k+1$ disjoint $k$-clique isolating sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03666 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Isolation partitions in graphs Zhang, Gang Yang, Weiling Jin, Xian'an Combinatorics 05C69, 05C15 Let $G$ be a graph and $k \geq 3$ an integer. A subset $D \subseteq V(G)$ is a $k$-clique (resp., cycle) isolating set of $G$ if $G-N[D]$ contains no $k$-clique (resp., cycle). In this paper, we prove that every connected graph with maximum degree at most $k$, except $k$-clique, can be partitioned into $k+1$ disjoint $k$-clique isolating sets, and that every connected claw-free subcubic graph, except 3-cycle, can be partitioned into four disjoint cycle isolating sets. As a consequence of the first result, every $k$-regular graph can be partitioned into $k+1$ disjoint $k$-clique isolating sets. |
| title | Isolation partitions in graphs |
| topic | Combinatorics 05C69, 05C15 |
| url | https://arxiv.org/abs/2411.03666 |