Geodesic
A spanning tree with a large number of pendant vertices
Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 63-72 
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/
@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},
     year = {2001},
     volume = {13},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/DM_2001_13_1_a2/
%G ru
%F DM_2001_13_1_a2

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.

[1] Zelinka B., “Finding a spanning tree of a graph with maximal number of terminal vertices”, Kybernetika, 9:5 (1973), 357–360 | MR | Zbl

[2] Karpov D. V., “Udalenie vershin iz svyaznogo grafa”, Modelirovanie i analiz informatsionnykh sistem, 6 (1999), 21–25

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR

[4] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[5] Ore O., Teoriya grafov, Nauka, Moskva, 1968 | MR