Broadcast independence and packing in certain classes of trees
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_ | 1866913383697088512 |
|---|---|
| author | Brewster, Richard C. McDonald, Kiara A. |
| author_facet | Brewster, Richard C. McDonald, Kiara A. |
| contents | Given a graph $G=(V,E)$ of diameter $d$, a broadcast is a function $f:V(G) \to \{ 0, 1, \dots, d \}$ where $f(v)$ is at most the eccentricity of $v$. A vertex $v$ is broadcasting if $f(v)>0$ and a vertex $u$ hears $v$ if $d(u,v) \leq f(v)$. A broadcast is independent if no broadcasting vertex hears another vertex and is a packing if no vertex hears more than one vertex. The weight of $f$ is $\sum_{v \in V} f(v)$. We find the maximum weight independent and packing broadcasts for perfect $k$-ary trees, spiders, and double spiders as a partial answer to a question posed by Ahmane et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05825 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Broadcast independence and packing in certain classes of trees Brewster, Richard C. McDonald, Kiara A. Combinatorics 05C70, 05C69 Given a graph $G=(V,E)$ of diameter $d$, a broadcast is a function $f:V(G) \to \{ 0, 1, \dots, d \}$ where $f(v)$ is at most the eccentricity of $v$. A vertex $v$ is broadcasting if $f(v)>0$ and a vertex $u$ hears $v$ if $d(u,v) \leq f(v)$. A broadcast is independent if no broadcasting vertex hears another vertex and is a packing if no vertex hears more than one vertex. The weight of $f$ is $\sum_{v \in V} f(v)$. We find the maximum weight independent and packing broadcasts for perfect $k$-ary trees, spiders, and double spiders as a partial answer to a question posed by Ahmane et al. |
| title | Broadcast independence and packing in certain classes of trees |
| topic | Combinatorics 05C70, 05C69 |
| url | https://arxiv.org/abs/2406.05825 |