2014/02/25 by Felix Joos, Dieter Rautenbach, Joos, Felix +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1402.6129
8 pages
arxiv created 2014/02/25 · openalex publication_date 2014/02/25 · arxiv updated 2014/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We characterize the graphs for which the independence number equals the packing number. As a consequence we obtain simple structural descriptions of the graphs for which (i) the distance-k-packing number equals the distance-2k-packing number, and (ii) the distance-k-matching number equals the distance-2k-matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49-55). For positive integers k1 and k2 with k1<k2 and \lceil(3k2+1)/2\rceil≤ 2k1+1, we prove that it is NP-hard to determine for a given graph whether its distance-k1-packing number equals its distance-k2-packing number.