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 GraphArticle

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 $P_3$-packing problem in subcubic graphs of different connectivity, improving earlier results of Kelmans and Mubayi. 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 $\delta \geq 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.


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 248 times.
This article's PDF has been downloaded 259 times.