Lower bounds on the $k$-limited packing number of a graph

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics and Applied Mathematics, University of Johannesburg Auckland Park, 2006 South Africa

2 Department of Mathematics, Shahed University, Tehran, Iran

Abstract

‎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‎.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 14 August 2025

Files

Share

How to cite

Statistics