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
NULL##NULL##NULL
Adrian Kosowski;Michal Malafiejski;Pawel Zyliński
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.
Wenying Xi;Wensong Lin, 2021, On maximum P3-packing in claw-free subcubic graphs, Journal of Combinatorial Optimization, 41, 3, pp. 694-709, 10.1007/s10878-021-00708-2.