آمار
| تعداد نشریات | 7 |
| تعداد شمارهها | 61 |
| تعداد مقالات | 468 |
| تعداد مشاهده مقاله | 545,678 |
| تعداد دریافت فایل اصل مقاله | 380,395 |
Girth, minimum degree, independence, and broadcast independence | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 4، شماره 2، زمستان 2019، صفحه 131-139 اصل مقاله (395 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2019.26346.1098 | ||
| نویسندگان | ||
Stephane Bessy1؛ Dieter Rautenbach  2
| ||
| 1LIRMM | ||
| 289069 Ulm, Germay | ||
| چکیده | ||
| An independent broadcast on a connected graph $G$ is a function $f:V(G)to mathbb{N}_0$ such that, for every vertex $x$ of $G$, the value $f(x)$ is at most the eccentricity of $x$ in $G$, and $f(x)>0$ implies that $f(y)=0$ for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$. The broadcast independence number $alpha_b(G)$ of $G$ is the largest weight $sumlimits_{xin V(G)}f(x)$ of an independent broadcast $f$ on $G$. It is known that $alpha(G)leq alpha_b(G)leq 4alpha(G)$ for every connected graph $G$, where $alpha(G)$ is the independence number of $G$. If $G$ has girth $g$ and minimum degree $delta$, we show that $alpha_b(G)leq 2alpha(G)$ provided that $ggeq 6$ and $deltageq 3$ or that $ggeq 4$ and $deltageq 5$. Furthermore, we show that, for every positive integer $k$, there is a connected graph $G$ of girth at least $k$ and minimum degree at least $k$ such that $alpha_b(G)geq 2left(1-frac{1}{k}right)alpha(G)$. Our results imply that lower bounds on the girth and the minimum degree of a connected graph $G$ can lower the fraction $frac{alpha_b(G)}{alpha(G)}$ from $4$ below $2$, but not any further. | ||
| کلیدواژه ها | ||
| broadcast independence؛ independence؛ packing | ||
|
آمار تعداد مشاهده مقاله: 250 تعداد دریافت فایل اصل مقاله: 134 |
||
