Zapiski Nauchnykh Seminarov POMI
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 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, 2012, Volume 406, Pages 67–94 (Mi znsl5290)

Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4

D. V. Karpov

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 1 and 3 and $t$ vertices of degree at least 4 has a spanning tree with at least $\frac13t+\frac14s+\frac32$ leaves. We present an infinite series of graphs showing that our bound is tight.

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

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

English version:
Journal of Mathematical Sciences (New York), 2014, 196:6, 768–783

Bibliographic databases:

UDC: 519.172.1

Citation: D. V. Karpov, “Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4”, Combinatorics and graph theory. Part V, Zap. Nauchn. Sem. POMI, 406, POMI, St. Petersburg, 2012, 67–94; J. Math. Sci. (N. Y.), 196:6 (2014), 768–783

Citation in format AMSBIB
\Bibitem{Kar12} \by D.~V.~Karpov \paper Spanning trees with many leaves: lower bounds in terms of number of vertices of degree~1, 3 and at least~4 \inbook Combinatorics and graph theory. Part~V \serial Zap. Nauchn. Sem. POMI \yr 2012 \vol 406 \pages 67--94 \publ POMI \publaddr St.~Petersburg \mathnet{http://mi.mathnet.ru/znsl5290} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3032176} \transl \jour J. Math. Sci. (N. Y.) \yr 2014 \vol 196 \issue 6 \pages 768--783 \crossref{https://doi.org/10.1007/s10958-014-1692-7} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84914098124} 

• http://mi.mathnet.ru/eng/znsl5290
• http://mi.mathnet.ru/eng/znsl/v406/p67

 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. E. N. Simarova, “A bound on the number of leaves in a spanning tree of a connected graph of minimal degree 6”, J. Math. Sci. (N. Y.), 236:5 (2019), 542–553
•  Number of views: This page: 91 Full text: 24 References: 14