|
This article is cited in 1 scientific paper (total 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.
Received: 25.05.2000 Revised: 05.02.2001
Citation:
D. V. Karpov, “A spanning tree with a large number of pendant vertices”, Diskr. Mat., 13:1 (2001), 63–72; Discrete Math. Appl., 11:2 (2002), 163–171
Linking options:
https://www.mathnet.ru/eng/dm273https://doi.org/10.4213/dm273 https://www.mathnet.ru/eng/dm/v13/i1/p63
|
Statistics & downloads: |
Abstract page: | 565 | Full-text PDF : | 341 | References: | 56 | First page: | 1 |
|