آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 117 |
| تعداد مقالات | 1,391 |
| تعداد مشاهده مقاله | 1,409,083 |
| تعداد دریافت فایل اصل مقاله | 1,376,093 |
Lower bounds on the $k$-limited packing number of a graph | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 23 مرداد 1404 اصل مقاله (355.89 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30589.2546 | ||
| نویسندگان | ||
| Michael A. Henning1؛ Nader Jafari Rad* 2 | ||
| 1Department of Mathematics and Applied Mathematics, University of Johannesburg Auckland Park, 2006 South Africa | ||
| 2Department of Mathematics, Shahed University, Tehran, Iran | ||
| چکیده | ||
| For a given integer $k \ge 1$, a subset $S$ of vertices of a graph $G$ is a $k$-limited packing if $|N_G[v] \cap S| \le k$ for all $v\in V(G)$, where $N_G[v]$ denotes the closed neighborhood of a vertex~$v$ in $G$. The $k$-limited packing number, $L_k(G)$, is the maximum cardinality of a $k$-limited packing in $G$. In this paper we present a probabilistic lower bound for the $k$-limited packing number of a graph. In particular we improve a previous lower bound given in [Discrete Appl. Math. 184 (2015), 146--153]. We also present a randomized algorithm for the $k$-limited packing number of a graph. | ||
| کلیدواژه‌ها | ||
| $k$-limited packing number؛ Probabilistic methods؛ domination | ||
| مراجع | ||
|
[1] N. Alon and J.H. Spencer, The Probabilistic Method, John Wiley & Sons, 2016.
[2] P.N. Balister, B. Bollobás, and K. Gunderson, Limited packings of closed neighbourhoods in graphs, arXiv preprint arXiv:1501.01833 (2015).
[3] A. Gagarin and V. Zverovich, The probabilistic approach to limited packings in graphs, Discrete Appl. Math. 184 (2015), 146–153. https://doi.org/10.1016/j.dam.2014.11.017
[4] R. Gallant, G. Gunther, B.L. Hartnell, and D.F. Rall, Limited packings in graphs, Discrete Appl. Math. 158 (2010), no. 12, 1357–1364. https://doi.org/10.1016/j.dam.2009.04.014
[5] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, vol. 64, Springer Cham, 2020.
[6] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Structures of Domination in Graphs, vol. 66, Springer Cham, 2021.
[7] M.A. Henning and P.J. Slater, Open packing in graphs, J. Comb. Math. Comb. Comput. 29 (1999), 3–16.
[8] S.M. Hosseini Moghaddam, D.A. Mojdeh, and B. Samadi, Limited packing vs tuple domination in graphs, Fasciculi Math. 56 (2016), no. 1, 121–127. http://dx.doi.org/10.1515/fascmath-2016-0008
[9] M. Mohammadi, N. Jafari Rad, and M. Maghasedi, A new probabilistic lower bound on the limited packing number of a graph, Util. Math. 114 (2020), 249–254.
[10] D.A. Mojdeh, B. Samadi, and S.M. Hosseini Moghaddam, Limited packing vs tuple domination in graphs, Ars Combin. 133 (2017), 155–161.
[11] D.A. Mojdeh, B. Samadi, A. Khodkar, and H.R. Golmohammadi, On the packing numbers in graphs, Australas. J. Combin. 71 (2017), no. 3, 468–475.
[12] B. Samadi, On the k-limited packing numbers in graphs, Discrete Optim. 22 (2016), 270–276. https://doi.org/10.1016/j.disopt.2016.08.002 | ||
|
آمار تعداد مشاهده مقاله: 53 تعداد دریافت فایل اصل مقاله: 56 |
||