Spanning trees with few non-leaves

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)9-20
Number of pages12
JournalIsrael Journal of Mathematics
Volume256
Issue number1
DOIs
StatePublished - Sep 2023

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Spanning trees with few non-leaves'. Together they form a unique fingerprint.

Cite this