Comparing upper broadcast domination and boundary independence broadcast numbers of graphs

Document Type : Research Paper

Authors

1 Department of Mathematics and Statistics, University of Victoria, P. O.Box 3800, Victoria, Canada

2 Department of Adult Basic Education, Vancouver Island University Nanaimo,Canada

Abstract

A broadcast on a nontrivial connected graph $G=(V,E)$ is a function $f:V\rightarrow\{0, 1,\dots,d\}$, where $d=\operatorname{diam}(G)$, such that $f(v)\leq e(v)$ (the eccentricity of $v$) for all $v\in V$. The weight of $f$ is $\sigma(f)={\textstyle\sum_{v\in V}} f(v)$. A vertex $u$ hears $f$ from $v$ if $f(v)>0$ and $d(u,v)\leq f(v)$. A broadcast $f$ is dominating if every vertex of $G$ hears $f$. The upper broadcast domination number of $G$ is $\Gamma_{b}(G)=\max\left\{ \sigma(f):f\text{ is a minimal dominating broadcast of }G\right\}.$
 
A broadcast $f$ is boundary independent if, for any vertex $w$ that hears $f$ from vertices $v_{1},\ldots,v_{k},\ k\geq2$, the distance $d(w,v_{i})=f(v_{i})$ for each $i$. The maximum weight of a boundary independent broadcast is the boundary independence broadcast number $\alpha_{\operatorname{bn}}(G)$.
 
We compare $\alpha_{\operatorname{bn}}$ to $\Gamma_{b}$, showing that neither is an upper bound for the other. We show that the differences $\Gamma _{b}-\alpha_{\operatorname{bn}}$ and $\alpha_{\operatorname{bn}}-\Gamma_{b}$ are unbounded, the ratio $\alpha_{\operatorname{bn}}/\Gamma_{b}$ is bounded for all graphs, and $\Gamma_{b}/\alpha_{\operatorname{bn}}$ is bounded for bipartite graphs but unbounded in general.

Keywords

Main Subjects

References

[1] D. Ahmadi, G. H. Fricke, C. Schroeder, S. T. Hedetniemi and R. C. Laskar, Broadcast irredundance in graphs,
Congr. Numer., 224 (2015) 17–31.
[2] M. Ahmane, I. Bouchemakh and E. Sopena, On the broadcast independence number of caterpillars, Discrete Applied Math, 244 (2018) 20–356.
[3] M. Ahmane, I. Bouchemakh and E. Sopena, On the broadcast independence number of locally uniform 2-lobsters,
arXiv:1902.02998v1, 2019.
[4] S. Bessy and D. Rautenbach, Relating broadcast independence and independence, Discrete Math., 342 (2019) 7 pp.
[5] S. Bessy and D. Rautenbach, Girth, minimum degree, independence, and broadcast independence, Commun. Comb. Optim., 4 (2019) 131–139.
[6] I. Bouchemakh and N. Fergani, On the upper broadcast domination number, Ars Combin., 130 (2017) 151–161.
[7] I. Bouchemakh and M. Zemir, On the broadcast independence number of grid graph, Graphs Combin., 30 (2014)
83–100.
[8] S. Bouchouika, I. Bouchemakh and E. Sopena, Broadcasts on paths and cycles, Discrete Appl. Math., 283 (2020)
375–395.
[9] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, Chapman and Hall/CRC, Boca Raton, 2015.
[10] J. Dunbar, D. Erwin, T. Haynes, S. M. Hedetniemi and S. T. Hedetniemi, Broadcasts in graphs, Discrete Appl.
Math., 154 (2006) 59–75.
[11] D. Erwin, Cost domination in graphs. Doctoral dissertation, Western Michigan University, 2001.
[12] M. A. Henning, G. MacGillivray and F. Yang, Broadcast domination in graphs, Structures of domination in graphs,
Dev. Math., 66, Springer, Cham, (2021) 15–46
[13] E. Marchessault and C. M. Mynhardt, Lower boundary independent broadcasts in trees, submitted.
[14] C. M. Mynhardt and L. Neilson, Boundary independent broadcasts in graphs, J. Combin. Math. Combin. Comput., 116 (2021) 79–100.
[15] C. M. Mynhardt and A. Roux, Dominating and irredundant broadcasts in graphs, Discrete Appl. Math.,220 (2017)
80–90.
[16] L. Neilson, Broadcast independence in graphs, Doctoral dissertation, University of Victoria, 2019.

Files

History

  • Receive Date: 24 March 2021
  • Revise Date: 24 January 2023
  • Accept Date: 27 January 2023
  • Published Online: 01 March 2024

Share

How to cite

Statistics