[hal-01184370] Packing Three-Vertex Paths in a Subcubic Graph

In our paper we consider the P_3-packing problem in subcubic graphs of different connectivity, improving earlier results of Kelmans and Mubayi [KM04]. We show that there exists a P_3-packing of at least \lceil 3n/4\rceil vertices in any connected subcubic graph of order n>5 and minimum vertex degree δ ≥2, and that this bound is tight. The proof is constructive and implied by a linear-time algorithm. We use this result to show that any 2-connected cubic graph of order n>8 has a P_3-packing of at least \lceil 7n/9 \rceil vertices.

from HAL : Dernières publications http://ift.tt/1DQQNBm