Equality of distance packing numbers
Equality of distance packing numbers
复制标题
距离包装数相等
DOI：
10.1016/j.disc.2015.06.003
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
Felix Joos;D. Rautenbach
我们描述独立数等于包装数的图。因此，我们获得了图的简单结构描述，其中（i）距离-k-打包数等于距离-2 k-打包数，以及（ii）距离-k-匹配数等于距离-2 k-匹配数。最后的结果大大简化并扩展了 Cameron 和 Walker (2005) 先前的结果。对于正整数 k 1 和 k 2 且 k 1< k 2 且⌈(3 k 2+ 1)/2⌉≤ 2 k 1+ 1，我们证明对于给定图确定其距离-k 1-打包数是否等于其距离-k 2-打包数是NP困难的。
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-2 k-packing number, and (ii) the distance-k-matching number equals the distance-2 k-matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (2005). For positive integers k 1 and k 2 with k 1< k 2 and⌈(3 k 2+ 1)/2⌉≤ 2 k 1+ 1, we prove that it is NP-hard to determine for a given graph whether its distance-k 1-packing number equals its distance-k 2-packing number.