Comparing upper broadcast domination and boundary independence broadcast numbers of graphs

A broadcast on a nontrivial connected graph G=(V,E) is a function f:V\rightarrow\{۰, ۱,\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)>۰ 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_{۱},\ldots,v_{k},\ k\geq۲, 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