تقرير
On the Broadcast Independence Number of Circulant Graphs
| العنوان: | On the Broadcast Independence Number of Circulant Graphs |
|---|---|
| المؤلفون: | Laouar, Abdelamin, Bouchemakh, Isma, Sopena, Eric |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | An independent broadcast on a graph $G$ is a function $f: V \longrightarrow \{0,\ldots,{\rm diam}(G)\}$ such that $(i)$ $f(v)\leq e(v)$ for every vertex $v\in V(G)$, where $\operatorname{diam}(G)$ denotes the diameter of $G$ and $e(v)$ the eccentricity of vertex $v$, and $(ii)$ $d(u,v) > \max \{f(u), f(v)\}$ for every two distinct vertices $u$ and $v$ with $f(u)f(v)>0$. The broadcast independence number $\beta_b(G)$ of $G$ is then the maximum value of $\sum_{v \in V} f(v)$, taken over all independent broadcasts on $G$. We prove that every circulant graph of the form $C(n;1,a)$, $3\le a\le \lfloor\frac{n}{2} \rfloor$, admits an optimal $2$-bounded independent broadcast, that is, an independent broadcast~$f$ satisfying $f(v)\le 2$ for every vertex $v$, except when $n=2a+1$, or $n=2a$ and $a$ is even. We then determine the broadcast independence number of various classes of such circulant graphs, and prove that, for most of these classes, the equality $\beta_b(C(n;1,a)) = \alpha(C(n;1,a))$ holds, where $\alpha(C(n;1,a))$ denotes the independence number of $C(n;1,a)$. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2102.04094 |
| رقم الأكسشن: | edsarx.2102.04094 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |