DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Packing Three-Vertex Paths in a Subcubic Graph

Adrian Kosowski, Michał Małafiejski, Paweł Żyliński


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

Valid XHTML 1.0 Transitional