Spanning Trees with Many Leaves

DOI10.1137/0404010zbMath0734.05041WikidataQ106158567 ScholiaQ106158567MaRDI QIDQ3360890

Douglas B. West, Daniel J. Kleitman

Publication date: 1991

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0404010

zbMATH Keywords

spanning tree

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

Related Items

A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs, Spanning Trees with Many Leaves in Regular Bipartite Graphs, A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs, Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Leafy spanning trees in hypercubes, Spanning trees with many leaves, The 3-rainbow index and connected dominating sets, Upper bounds for the total rainbow connection of graphs, A \(9k\) kernel for nonseparating independent set in planar graphs, Kernel bounds for path and cycle problems, Improved bounds for spanning trees with many leaves, Max-leaves spanning tree is APX-hard for cubic graphs, Confronting intractability via parameters, On minimum degree, leaf number, traceability and Hamiltonicity in graphs, A 2-approximation algorithm for finding a spanning tree with maximum number of leaves, Some results on spanning trees, On graphs with few disjoint \(t\)-star minors, A new algorithm for finding trees with many leaves, Spanning trees: A survey, Connected domination number of a graph and its complement, The complexity ecology of parameters: An illustration using bounded max leaf number, 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, FPT algorithms and kernels for the directed \(k\)-leaf problem, Spanning trees in graphs of minimum degree 4 or 5, On the \(r\)-domination number of a graph, An exact algorithm for the maximum leaf spanning tree problem., Lower bounds on the number of leaves in spanning trees, Hamiltonicity, minimum degree and leaf number, Leaf number and Hamiltonian \(C_4\)-free graphs, Graphs with forbidden subgraphs and leaf number, Spanning paths in graphs, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, Bounds on the connected forcing number of a graph, Algorithmic meta-theorems for restrictions of treewidth, Bounds of the number of leaves of spanning trees in graphs without triangles, Bounds of the number of leaves of spanning trees, Constructing a spanning tree with many leaves, Modifying a graph using vertex elimination, Hardness and approximation results for black hole search in arbitrary networks, The graph motif problem parameterized by the structure of the input graph, On maximum leaf trees and connections to connected maximum cut problems, On spanning cycles, paths and trees, A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6, Minimum degree, leaf number and traceability, Kernel Bounds for Path and Cycle Problems, Minimum Degree and Dominating Paths, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree