Geodesic
Lower Bounds For Induced Forests in Cubic Graphs
Canadian mathematical bulletin, Tome 30 (1987) no. 2, pp. 193-199

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

DOI

If G is a connected cubic graph with ρ vertices, ρ > 4, then G has a vertex-induced forest containing at least (5ρ - 2)/8 vertices. In case G is triangle-free, the lower bound is improved to (2ρ — l)/3. Examples are given to show that no such lower bound is possible for vertex-induced trees.
DOI : 10.4153/CMB-1987-028-5
Mots-clés : 05 
Bondy, J. A.; Hopkins, Glenn; Staton, William. Lower Bounds For Induced Forests in Cubic Graphs. Canadian mathematical bulletin, Tome 30 (1987) no. 2, pp. 193-199. doi: 10.4153/CMB-1987-028-5
@article{10_4153_CMB_1987_028_5,
     author = {Bondy, J. A. and Hopkins, Glenn and Staton, William},
     title = {Lower {Bounds} {For} {Induced} {Forests} in {Cubic} {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {193--199},
     year = {1987},
     volume = {30},
     number = {2},
     doi = {10.4153/CMB-1987-028-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-028-5/}
}
TY  - JOUR
AU  - Bondy, J. A.
AU  - Hopkins, Glenn
AU  - Staton, William
TI  - Lower Bounds For Induced Forests in Cubic Graphs
JO  - Canadian mathematical bulletin
PY  - 1987
SP  - 193
EP  - 199
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-028-5/
DO  - 10.4153/CMB-1987-028-5
ID  - 10_4153_CMB_1987_028_5
ER  - 
%0 Journal Article
%A Bondy, J. A.
%A Hopkins, Glenn
%A Staton, William
%T Lower Bounds For Induced Forests in Cubic Graphs
%J Canadian mathematical bulletin
%D 1987
%P 193-199
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-028-5/
%R 10.4153/CMB-1987-028-5
%F 10_4153_CMB_1987_028_5

Cité par Sources :