TY - JOUR

T1 - Spanning trees with few non-leaves

AU - Alon, Noga

N1 - Publisher Copyright:
© 2023, The Hebrew University of Jerusalem.

PY - 2023/9

Y1 - 2023/9

N2 - Let f (n, k) denote the smallest number so that every connected graph with n vertices and minimum degree at least k contains a spanning tree in which the number of non-leaves is at most f (n, k). An early result of Linial and Sturtevant asserting that f (n, 3) = 3n/4 + O(1) and a related conjecture suggested by Linial led to a significant amount of work studying this function. It is known that for n much larger than k, f(n,k)≥nk+1(1−ε(k))ln(k+1) , where ε(k) tends to zero as k tends to infinity. Here we prove that f(n,k)≤nk+1(ln(k+1)+4)−2 . This improves the error term in the best known upper bound for the function, due to Caro, West and Yuster, which is f(n,k)≤nk+1(ln(k+1)+0.5ln(k+1)+145) . The proof provides an efficient deterministic algorithm for finding such a spanning tree in any given input graph satisfying the assumptions.

AB - Let f (n, k) denote the smallest number so that every connected graph with n vertices and minimum degree at least k contains a spanning tree in which the number of non-leaves is at most f (n, k). An early result of Linial and Sturtevant asserting that f (n, 3) = 3n/4 + O(1) and a related conjecture suggested by Linial led to a significant amount of work studying this function. It is known that for n much larger than k, f(n,k)≥nk+1(1−ε(k))ln(k+1) , where ε(k) tends to zero as k tends to infinity. Here we prove that f(n,k)≤nk+1(ln(k+1)+4)−2 . This improves the error term in the best known upper bound for the function, due to Caro, West and Yuster, which is f(n,k)≤nk+1(ln(k+1)+0.5ln(k+1)+145) . The proof provides an efficient deterministic algorithm for finding such a spanning tree in any given input graph satisfying the assumptions.

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

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

U2 - 10.1007/s11856-023-2499-3

DO - 10.1007/s11856-023-2499-3

M3 - Article

AN - SCOPUS:85173697654

SN - 0021-2172

VL - 256

SP - 9

EP - 20

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 1

ER -