Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms

DOI10.1007/978-3-540-78773-0_46MaRDI QIDQ5458557zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Florian Zickfeld

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.2760

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: It is known that graphs on n vertices with minimum degree at least 3 have spanning trees with at least n/4+2 leaves and that this can be improved to (n+4)/3 for cubic graphs without the diamond K_4-e as a subgraph. We generalize the second result by proving that every graph with minimum degree at least 3, without diamonds and certain subgraphs called blossoms, has a spanning tree with at least (n+4)/3 leaves, and generalize this further by allowing vertices of lower degree. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n/3+c. We use the new bound to obtain a simple FPT algorithm, which decides in O(m)+O^*(6.75^k) time whether a graph of size m has a spanning tree with at least k leaves. This improves the best known time complexity for MAX LEAF SPANNING TREE.

Recommendations

• Improved bounds for spanning trees with many leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning Trees with Many Leaves
• Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4
• Constructing a spanning tree with many leaves

Cites work

• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• On Linear Time Minor Tests with Depth-First Search
• Parametrized complexity theory.
• Spanning Trees with Many Leaves
• Spanning trees with many leaves in cubic graphs

Cited in

(22)

• Lower bounds on the number of leaves in spanning trees
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• Spanning 3-ended trees in almost claw-free graphs
• The existence of spanning ended system on claw-free graphs
• Bounds of the number of leaves of spanning trees in graphs without triangles
• Bounds of the number of leaves of spanning trees
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• Improved bounds for spanning trees with many leaves
• Max-leaves spanning tree is APX-hard for cubic graphs
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Spotting trees with few leaves
• Leafy spanning arborescences in DAGs
• Leafy spanning arborescences in DAGs
• A new algorithm for finding trees with many leaves
• An exact algorithm for the maximum leaf spanning tree problem
• Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves
• Spanning trees: A survey
• On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves
• 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

This page was built for publication: Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms

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