Equality of distance packing numbers

DOI10.1016/J.DISC.2015.06.003MaRDI QIDQ2515579zbMATH OpenOpenAlexFDO

Publication date 5 August 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.6129

matching independent set induced matching packing

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 (The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49-55). For positive integers

k_{1}

and

k_{2}

with

k_{1} < k_{2}

and

l c e i l (3 k_{2} + 1) / 2 c e i l l e q 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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Equality of distance packing numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515579)