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

Zap. Nauchn. Sem. POMI, 2011 Volume 391, Pages 18–34 (Mi znsl4566)

This article is cited in 7 papers

Bounds of a number of leaves of spanning trees

A. V. Bankevicha, D. V. Karpovb

a Saint-Petersburg State University, Saint-Petersburg, Russia
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: We prove that every connected graph with $s$ vertices of degree not 2 has a spanning tree with at least $\frac14(s-2)+2$ leaves.
Let $G$ be a connected graph of girth $g$ with $v$ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. We prove that $G$ has a spanning tree with at least $\alpha_{g,k}(v(G)-k-2)+2$ leaves, where $\alpha_{g,k}=\frac{[\frac{g+1}2]}{[\frac{g+1}2](k+3)+1}$ for $k<g-2$; $\alpha_{g,k}(v(G)-k-2)+2$ for $k\ge g-2$.
We present infinite series of examples showing that all these bounds are exact.

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

UDC: 519.172.1

Received: 15.09.2011


 English version:
Journal of Mathematical Sciences (New York), 2012, 184:5, 564–572

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024