RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2010 Volume 381, Pages 78–87 (Mi znsl3853)

This article is cited in 6 papers

Spanning trees with many leaves

D. V. Karpov

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences

Abstract: Let maximal chain of vertices of degree 2 in the graph $G$ consists of $k>0$ vertices. We prove that $G$ has a spanning tree with more than $\frac{v(G)}{2k+4}$ leaves (we denote by $v(G)$ the number of vertices of the graph $G$). We present an infinite serie of examples showing that the constant $\frac1{2k+4}$ cannot be enlarged. Bibl. 7 titles.

Key words and phrases: spanning tree, leaves, number of leaves.

UDC: 519.172.1

Received: 23.08.2010


 English version:
Journal of Mathematical Sciences (New York), 2011, 179:5, 616–620

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024