The $n/2$-bound for locating-dominating sets in subcubic graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911935191056384 |
|---|---|
| author | Chakraborty, Dipayan Hakanen, Anni Lehtilä, Tuomo |
| author_facet | Chakraborty, Dipayan Hakanen, Anni Lehtilä, Tuomo |
| contents | The location-domination number is conjectured to be at most half of the order for twin-free graphs with no isolated vertices. We prove that this conjecture holds and is tight for subcubic graphs. We also show that the same upper bound holds for subcubic graphs with open twins of degree 3 and closed twins of any degree, but not for subcubic graphs with open twins of degree 1 or 2. These results then imply that the same upper bound holds for all cubic graphs (with or without twins) except $K_4$ and $K_{3,3}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19278 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The $n/2$-bound for locating-dominating sets in subcubic graphs Chakraborty, Dipayan Hakanen, Anni Lehtilä, Tuomo Combinatorics The location-domination number is conjectured to be at most half of the order for twin-free graphs with no isolated vertices. We prove that this conjecture holds and is tight for subcubic graphs. We also show that the same upper bound holds for subcubic graphs with open twins of degree 3 and closed twins of any degree, but not for subcubic graphs with open twins of degree 1 or 2. These results then imply that the same upper bound holds for all cubic graphs (with or without twins) except $K_4$ and $K_{3,3}$. |
| title | The $n/2$-bound for locating-dominating sets in subcubic graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.19278 |