Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
En palabras de los autores
We give a polynomial-time algorithm that constructs, in every connected -vertex graph of minimum degree at least , a spanning tree with at least leaves. No bound specific to minimum degree was known: the best bound available for this class was , inherited from Simarova's theorem for minimum degree~. The algorithm and its analysis are carried out for an arbitrary minimum degree , and yield a recursion that gives an explicit lower bound on the number of leaves for every . The resulting bounds improve all previously known ones for every ; for they are , and , and they are tabulated for at the end of the paper.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 28 de septiembre. arXiv. Preprint, todavía sin revisión por pares.