Packing Three-Vertex Paths in a Subcubic Graph
Adrian Kosowski, Michał Małafiejski, Paweł Żyliński
Abstract
In our paper we consider the P3-packing problem in subcubic graphs of different connectivity, improving earlier results of Kelmans and Mubayi [KM04]. We show that there exists a P3-packing of at least ⌈3n/4⌉ 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 P3-packing of at least ⌈7n/9 ⌉ vertices.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page