Date

Back to the event list

Forschungssem­in­ar Graphen­the­or­ie: Car­ol T. Zam­firescu (Ghent Uni­ver­sity, Bel­gi­um), (zoom talk) "Span­ning trees with many dif­fer­ent num­bers of leaves"

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.