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 18–34 (Mi znsl4566)

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.

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

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

Document Type: Article
UDC: 519.172.1

Citation: A. V. Bankevich, D. V. Karpov, “Bounds of a number of leaves of spanning trees”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 18–34; J. Math. Sci. (N. Y.), 184:5 (2012), 564–572

Citation in format AMSBIB
\Bibitem{BanKar11} \by A.~V.~Bankevich, D.~V.~Karpov \paper Bounds of a~number of leaves of spanning trees \inbook Combinatorics and graph theory. Part~III \serial Zap. Nauchn. Sem. POMI \yr 2011 \vol 391 \pages 18--34 \publ POMI \publaddr St.~Petersburg \mathnet{http://mi.mathnet.ru/znsl4566} \transl \jour J. Math. Sci. (N. Y.) \yr 2012 \vol 184 \issue 5 \pages 564--572 \crossref{https://doi.org/10.1007/s10958-012-0881-5} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84884301886} 

• http://mi.mathnet.ru/eng/znsl4566
• http://mi.mathnet.ru/eng/znsl/v391/p18

 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. Bankevich A. V., “Bounds of a number of leaves of spanning trees in graphs without triangles”, J. Math. Sci. (N. Y.), 184:5 (2012), 557–563
2. D. V. Karpov, “Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree 3 and at least 4”, J. Math. Sci. (N. Y.), 196:6 (2014), 747–767
3. 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
4. V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, J. Appl. Industr. Math., 10:1 (2016), 1–6
5. D. V. Karpov, “Lower bounds on the number of leaves in spanning trees”, J. Math. Sci. (N. Y.), 232:1 (2018), 36–43
•  Number of views: This page: 106 Full text: 26 References: 5