Geodesic
A spanning tree with a large number of pendant vertices
Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 63-72

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that for every connected graph $G(V,E)$ with no adjacent vertices of degree 2 there exists a spanning tree with more than $|V|/5$ end vertices. We describe a polynomial algorithm of constructing such a tree. The constant 1/5 cannot be improved. 
@article{DM_2001_13_1_a2,
     author = {D. V. Karpov},
     title = {A spanning tree with a large number of pendant vertices},
     journal = {Diskretnaya Matematika},
     pages = {63--72},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_1_a2/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - A spanning tree with a large number of pendant vertices
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 63
EP  - 72
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_1_a2/
LA  - ru
ID  - DM_2001_13_1_a2
ER  - 
%0 Journal Article
%A D. V. Karpov
%T A spanning tree with a large number of pendant vertices
%J Diskretnaya Matematika
%D 2001
%P 63-72
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2001_13_1_a2/
%G ru
%F DM_2001_13_1_a2
D. V. Karpov. A spanning tree with a large number of pendant vertices. Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 63-72. http://geodesic.mathdoc.fr/item/DM_2001_13_1_a2/