RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zap. Nauchn. Sem. POMI: Year: Volume: Issue: Page: Find

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

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.

Full text: PDF file (235 kB)
References: PDF file   HTML file

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

Document Type: Article
UDC: 519.172.1

Citation: Bankevich A. V., “Bounds of a number of leaves of spanning trees in graphs without triangles”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 5–17; J. Math. Sci. (N. Y.), 184:5 (2012), 557–563

Citation in format AMSBIB
\Bibitem{Ban11} \by Bankevich~A.~V. \paper Bounds of a~number of leaves of spanning trees in graphs without triangles \inbook Combinatorics and graph theory. Part~III \serial Zap. Nauchn. Sem. POMI \yr 2011 \vol 391 \pages 5--17 \publ POMI \publaddr St.~Petersburg \mathnet{http://mi.mathnet.ru/znsl4565} \transl \jour J. Math. Sci. (N. Y.) \yr 2012 \vol 184 \issue 5 \pages 557--563 \crossref{https://doi.org/10.1007/s10958-012-0880-6} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84884317032} 

• http://mi.mathnet.ru/eng/znsl4565
• http://mi.mathnet.ru/eng/znsl/v391/p5

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. D. V. Karpov, “Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4”, J. Math. Sci. (N. Y.), 196:6 (2014), 768–783
2. D. V. Karpov, “Nizhnie otsenki kolichestva listev v ostovnykh derevyakh”, Kombinatorika i teoriya grafov. VIII, Zap. nauchn. sem. POMI, 450, POMI, SPb., 2016, 62–73
•  Number of views: This page: 63 Full text: 17 References: 11