On $k$-(total) limited packing in graphs

Document Type : Original paper

Authors

Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

Abstract

A set $B\subseteq V(G)$ is called a $k$-total limited packing set in a graph $G$ if $|B\cap N(v)|\leq k$ for any vertex $v\in V(G)$. The $k$-total limited packing number $L_{k,t}(G)$ is the maximum cardinality of a $k$-total limited packing set in $G$. Here, we give some results on the $k$-total limited packing number of graphs emphasizing trees, especially when $k=2$. We also study the $2$-(total) limited packing number of some product graphs.



A $k$-limited packing partition ($k$LPP) of graph $G$ is a partition of $V(G)$ into $k$-limited packing sets. The minimum cardinality of a $k$LPP is called the $k$LPP number of $G$ and is denoted by $\chi_{\times k}(G)$, and we obtain some results for this parameter.

Keywords

Main Subjects

References

[1] A.S. Ahmadi, N. Soltankhah, and B. Samadi, Limited packings: Related vertex partitions and duality issues, Appl. Math. Comput. 472 (2024), Article ID: 128613.  https://doi.org/10.1016/j.amc.2024.128613
[2] X. Bai, H. Chang, and X. Li, More on limited packings in graphs, J. Comb. Optim. 40 (2020), no. 2, 412–430. https://doi.org/10.1007/s10878-020-00606-z
[3] P.N. Balister, B. Bollobás, and K. Gunderson, Limited packings of closed neighbourhoods in graphs, arXiv preprint arXiv:1501.01833 (2015).
[4] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261. https://doi.org/10.1002/net.3230070305
[5] M.P. Dobson, V. Leoni, and G. Nasini, The multiple domination and limited packing problems in graphs, Inform. Process. Lett. 111 (2011), no. 23-24, 1108–1113. https://doi.org/10.1016/j.ipl.2011.09.002
[6] 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
[7] 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
[8] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[9] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, Cham, 2023.
[10] S.M. Hosseini Moghaddam, D.A. Mojdeh, and B. Samadi, Total limited packing in graphs, Fasc. Math. 56 (2016), 121–127.  https://doi.org/10.1515/fascmath-2016-0008
[11] V. Leoni and G. Nasini, Limited packing and multiple domination problems: Polynomial time reductions, Discrete Appl. Math. 164 (2014), 547–553. https://doi.org/10.1016/j.dam.2013.10.023
[12] D.A. Mojdeh, I. Peterin, B. Samadi, and I.G. Yero, (Open) packing number of some graph products, Discrete Math. Theor. Comput. Sci. 22 (2020), no. 4, Article ID: #1  https://doi.org/10.23638/DMTCS-22-4-1
[13] D.F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 (2005), no. 1-2, 35–44. http://doi.org/10.7151/dmgt.1257
[14] B. Samadi, On the k-limited packing numbers in graphs, Discrete Optim. 22 (2016), no. Part B, 270–276. https://doi.org/10.1016/j.disopt.2016.08.002
[15] D.B. West, Introduction to Graph Theory (second edition), Prentice hall Upper Saddle River, USA, 2001.
Communications in Combinatorics and Optimization
Volume 11, Issue 3
September 2026
Pages 995-1011

Files

Share

How to cite

Statistics