Adrian Kosowski ; Michal Malafiejski ; Pawel Zyliński - Packing Three-Vertex Paths in a Subcubic Graph

dmtcs:3413 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3413
Packing Three-Vertex Paths in a Subcubic GraphConference paper

Authors: Adrian Kosowski 1; Michal Malafiejski 1; Pawel Zyliński 2

  • 1 Department of Algorithms and Systems Modelling [ETI GUT]
  • 2 Instytut Matematyki [Gdańsk]

In our paper we consider the P3-packing problem in subcubic graphs of different connectivity, improving earlier results of Kelmans and Mubayi. 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: three-vertex paths,subcubic graphs,path packing,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 284 times.
This article's PDF has been downloaded 295 times.