Girth, minimum degree, independence, and broadcast independence

Bessy, Stephane; Rautenbach, Dieter

doi:10.22049/cco.2019.26346.1098

تعداد نشریات	6
تعداد شماره‌ها	121
تعداد مقالات	1,448
تعداد مشاهده مقاله	1,555,249
تعداد دریافت فایل اصل مقاله	1,459,464

	Girth, minimum degree, independence, and broadcast independence
Communications in Combinatorics and Optimization
مقاله 6، دوره 4، شماره 2، اسفند 2019، صفحه 131-139 اصل مقاله (395.24 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2019.26346.1098
نویسندگان
Stephane Bessy¹؛ Dieter Rautenbach^* ²
¹LIRMM
²89069 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 $\sum_{x\in V(G)}f(x)$ of an independent broadcast $f$ on $G$. It is known that $\alpha(G)\leq \alpha_b(G)\leq 4\alpha(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 2\alpha(G)$ provided that $g\geq 6$ and $\delta\geq 3$ or that $g\geq 4$ and $\delta\geq 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 2\left(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

مراجع
[1] M. Ahmane, I. Bouchemakh, and E. Sopena, On the broadcast independence number of caterpillars, Discrete Appl. Math. 244 (2018), 20–35. [2] S. Bessy and D. Rautenbach, Algorithmic aspects of broadcast independence, arXiv 1809.07248. [3] S. Bessy and D. Rautenbach, Relating broadcast independence and independence, Manuscript 2018. [4] I. Bouchemakh and M. Zemir, On the broadcast independence number of grid graph, Graphs Combin. 30 (2014), no. 1, 83–100. [5] R. Diestel, Graduate Texts in Mathematics, Springer-Verlag New York, Incorporated, 2000. [6] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006), no. 1, 59–75. [7] P. Erdős, Graph theory and probability II, Canad. J. Math. 13 (1961), 346–352. [8] D.J. Erwin, Cost domination in graphs, (Ph.D. thesis), Western Michigan University, 2001. [9] F. Joos and D. Rautenbach, Equality of distance packing numbers, Discrete Math. 338 (2015), no. 12, 2374–2377. [10] J. Topp and L. Volkmann, On packing and covering numbers of graphs, Discrete Math. 96 (1991), no. 3, 229–238.
آمار تعداد مشاهده مقاله: 935 تعداد دریافت فایل اصل مقاله: 1,005

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

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

آمار

Girth, minimum degree, independence, and broadcast independence