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

Zap. Nauchn. Sem. POMI, 2011 Volume 391, Pages 5–17 (Mi znsl4565)

This article is cited in 5 papers

Bounds of a number of leaves of spanning trees in graphs without triangles

Bankevich A. V.

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: We prove that for every connected graph with girth at least $4$ and $s$ vertices of degree not $2$ there is a spanning tree with at least $\frac13(s-2)+2$ leaves. We describe series of examples showing that this bound is tight. This result, together with the bound for graphs with no limit on the girth (in such graphs one can construct a spanning tree with at least $\frac14(s-2)+2$ leaves) leads to the hypothesis that for a graph with girth at least $g$, there exists a spanning tree with at least $\frac{g-2}{2g-2}(s-2)+2$ leaves. We prove that this conjecture fails for $g\ge10$ and the bound cannot exceed $\frac7{16}s+\frac12$.

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

UDC: 519.172.1

Received: 28.09.2011


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024