Back to Search
Start Over
Limited packings: Related vertex partitions and duality issues.
- Source :
-
Applied Mathematics & Computation . Jul2024, Vol. 472, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- A k -limited packing partition (k LP partition) of a graph G is a partition of V (G) into k -limited packing sets. We consider the k LP partitions with minimum cardinality (with emphasis on k = 2). The minimum cardinality is called k LP partition number of G and denoted by χ × k (G). This problem is the dual problem of k -tuple domatic partitioning as well as a generalization of the well-studied 2-distance coloring problem in graphs. We give the exact value of χ × 2 for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in 1998. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between 2TLP number and 2LP number with emphasis on trees. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH coloring
*GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 472
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 176196316
- Full Text :
- https://doi.org/10.1016/j.amc.2024.128613