TY - JOUR

T1 - Bounds of the number of leaves of spanning trees

AU - Bankevich, A. V.

AU - Karpov, D. V.

PY - 2012/8/1

Y1 - 2012/8/1

N2 - We prove that every connected graph with s vertices of degree not 2 has a spanning tree with at least 1/4(s- 2) + 2 leaves. Let G be a connected graph of girth g with υ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph G does not exceed k ≥ 1. We prove that G has a spanning tree with at least αg,k(υ(G) - k - 2) + 2 leaves, where αg,k[g + 1/2]/[g + 1/2](k+3)+1 for k < g - 2; αg,k = g-2/(g-1)(k+2) for k ≥ g - 2. We present infinite series of examples showing that all these bounds are tight. Bibliography: 12 titles.

AB - We prove that every connected graph with s vertices of degree not 2 has a spanning tree with at least 1/4(s- 2) + 2 leaves. Let G be a connected graph of girth g with υ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph G does not exceed k ≥ 1. We prove that G has a spanning tree with at least αg,k(υ(G) - k - 2) + 2 leaves, where αg,k[g + 1/2]/[g + 1/2](k+3)+1 for k < g - 2; αg,k = g-2/(g-1)(k+2) for k ≥ g - 2. We present infinite series of examples showing that all these bounds are tight. Bibliography: 12 titles.

UR - http://www.scopus.com/inward/record.url?scp=84884301886&partnerID=8YFLogxK

U2 - 10.1007/s10958-012-0881-5

DO - 10.1007/s10958-012-0881-5

M3 - Article

AN - SCOPUS:84884301886

VL - 184

SP - 564

EP - 572

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 5

ER -