Comparing upper broadcast domination and boundary independence broadcast numbers of graphs

Mynhardt, Kieka; Neilson, Linda

doi:10.22108/toc.2023.127904.1836

تعداد نشریات	43
تعداد شماره‌ها	1,713
تعداد مقالات	14,045
تعداد مشاهده مقاله	33,985,207
تعداد دریافت فایل اصل مقاله	13,610,483

	Comparing upper broadcast domination and boundary independence broadcast numbers of graphs
Transactions on Combinatorics
مقاله 8، دوره 13، شماره 1، خرداد 2024، صفحه 105-126 اصل مقاله (630.59 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.127904.1836
نویسندگان
Kieka Mynhardt^* ¹؛ Linda Neilson²
¹Department of Mathematics and Statistics, University of Victoria, P. O.Box 3800, Victoria, Canada
²Department of Adult Basic Education, Vancouver Island University Nanaimo,Canada
چکیده
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.
کلیدواژه‌ها
broadcast domination؛ broadcast independence؛ hearing independent broadcast؛ boundary independent broadcast

مراجع
[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.
آمار تعداد مشاهده مقاله: 192 تعداد دریافت فایل اصل مقاله: 296

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Comparing upper broadcast domination and boundary independence broadcast numbers of graphs