TY - JOUR

T1 - Lower Bounds on the Number of Leaves in Spanning Trees

AU - Karpov, D. V.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - Let G be a connected graph on n ≥ 2 vertices with girth at least g such that the length of a maximal chain of successively adjacent vertices of degree 2 in G does not exceed k ≥ 1. Denote by u(G) the maximum number of leaves in a spanning tree of G. We prove that u(G) ≥ αg,k(υ(G) − k − 2) + 2 where αg,1=[g+12]4[g+12]+1 and αg,k=12k+2 for k ≥ 2. We present an infinite series of examples showing that all these bounds are tight.

AB - Let G be a connected graph on n ≥ 2 vertices with girth at least g such that the length of a maximal chain of successively adjacent vertices of degree 2 in G does not exceed k ≥ 1. Denote by u(G) the maximum number of leaves in a spanning tree of G. We prove that u(G) ≥ αg,k(υ(G) − k − 2) + 2 where αg,1=[g+12]4[g+12]+1 and αg,k=12k+2 for k ≥ 2. We present an infinite series of examples showing that all these bounds are tight.

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

U2 - 10.1007/s10958-018-3857-2

DO - 10.1007/s10958-018-3857-2

M3 - Article

AN - SCOPUS:85047306988

VL - 232

SP - 36

EP - 43

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 1

ER -