RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2001 Volume 13, Issue 1, Pages 63–72 (Mi dm273)

This article is cited in 1 paper

A spanning tree with a large number of pendant vertices

D. V. Karpov


Abstract: 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.

UDC: 519.1

Received: 25.05.2000
Revised: 05.02.2001

DOI: 10.4213/dm273


 English version:
Discrete Mathematics and Applications, 2002, 11:2, 163–171

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025