Geodesic
Packing Three-Vertex Paths in a Subcubic Graph
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a22,
     author = {Kosowski, Adrian and Malafiejski, Michal and Zyli\'nski, Pawel},
     title = {Packing {Three-Vertex} {Paths} in a {Subcubic} {Graph}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3413},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3413/}
}
TY  - JOUR
AU  - Kosowski, Adrian
AU  - Malafiejski, Michal
AU  - Zyliński, Pawel
TI  - Packing Three-Vertex Paths in a Subcubic Graph
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3413/
DO  - 10.46298/dmtcs.3413
LA  - en
ID  - DMTCS_2005_special_250_a22
ER  - 
%0 Journal Article
%A Kosowski, Adrian
%A Malafiejski, Michal
%A Zyliński, Pawel
%T Packing Three-Vertex Paths in a Subcubic Graph
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3413/
%R 10.46298/dmtcs.3413
%G en
%F DMTCS_2005_special_250_a22
Kosowski, Adrian; Malafiejski, Michal; Zyliński, Pawel. Packing Three-Vertex Paths in a Subcubic Graph. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3413. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3413/

Cité par Sources :