For­schungs­se­mi­nar Gra­phen­the­o­rie: Ca­rol T. Zam­fi­res­cu (Ghent Uni­ver­si­ty, Bel­gi­um), (zoom talk) "Span­ning trees with ma­ny dif­fe­rent num­bers of lea­ves"

Abstract: Let G be a connected graph and L(G) the set of all integers k such that G contains a spanning tree with exactly k leaves. In this talk we give a short proof of the fact that for a connected graph G, the set L(G) is contiguous. We then discuss a few consequences of this result, both structural and algorithmic. We also present bounds for f(n), which we define to be the largest integer k such that every plane 4-connected triangulation on n vertices contains a spanning tree with at least k leaves. This talk is based on joint work with Kenta Noguchi (Tokyo University of Science, Japan).


If you are interested in participating online (either regularly or only in a specific lecture), please contact Yulai Ma or Eckhard Steffen in advance so that the participation link can be shared.