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 University Press

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

[1] 1. Behzad, M., Chartrand, G., and Lesniak-Foster, L., Graphs and Digraphs (Wadsworth, 1979), p. 10. Google Scholar

[2] 2. Jaegar, F., On vertex-induced forests in cubic graphs, Proc. 5th S.-E. Conf. Combinatorics, Graph Theory, and Computing (1974) 501–512. Google Scholar

[3] 3. Payan, C. and Sakarovitch, M., Ensembles cycliquement stables et graphes cubiques, Colloque sur la théorie des Graphes (Paris, 1974) Cahiers Centre Études Recherche Opér. 17 (1975) 319–343. Google Scholar

[4] 4. Staton, W., Induced forests in cubic graphs, Discrete Mathematics 49 (1984) 175-178. Google Scholar

Cité par Sources :