|
|
|
|
comparing upper broadcast domination and boundary independence broadcast numbers of graphs
|
|
|
|
|
|
|
|
نویسنده
|
mynhardt kieka ,neilson linda
|
|
منبع
|
transactions on combinatorics - 2024 - دوره : 13 - شماره : 1 - صفحه:105 -126
|
|
چکیده
|
A broadcast on a nontrivial connected graph $g=(v,e)$ is a function $f:vrightarrow{0, 1,dots,d}$, where $d=operatorname{diam}(g)$, such that $f(v)leq e(v)$ (the eccentricity of $v$) for all $vin v$. the weight of $f$ is $sigma(f)={textstylesum_{vin 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)=maxleft{ sigma(f):ftext{ is a minimal dominating broadcast of }gright}.$ a broadcast $f$ is boundary independent if, for any vertex $w$ that hears $f$ from vertices $v_{1},ldots,v_{k}, kgeq2$, 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
|
|
آدرس
|
university of victoria, department of mathematics and statistics, canada, vancouver island university, department of adult basic education, canada
|
|
پست الکترونیکی
|
linda.neilson@viu.ca
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|