Improved bounds for spanning trees with many leaves

DOI10.1016/J.DISC.2011.11.043MaRDI QIDQ409458zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Florian Zickfeld

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.11.043

zbMATH Keywords

lower boundspanning treemaximum number of leaves

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Recommendations

• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4
• Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4
• Spanning trees with many leaves

Cites work

• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A new algorithm for finding trees with many leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Connected Domination and Spanning Trees with Many Leaves
• Geometric and combinatorial structures on graphs
• Mathematical Foundations of Computer Science 2003
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Parametrized complexity theory.
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning trees in graphs of minimum degree 4 or 5
• Spanning trees with many leaves
• Spanning trees with many leaves in cubic graphs

Cited in

(9)

• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Flexible List Colorings in Graphs with Special Degeneracy Conditions
• A Simple 2-Approximation for Maximum-Leaf Spanning Tree
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• Flexible list colorings in graphs with special degeneracy conditions
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• Connected domination
• Spanning trees with few non-leaves

This page was built for publication: Improved bounds for spanning trees with many leaves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409458)