Spanning Trees with Many Leaves

DOI10.1137/0404010zbMath0734.05041OpenAlexW2011105641WikidataQ106158567 ScholiaQ106158567MaRDI QIDQ3360890

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

Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (66)

The 3-rainbow index and connected dominating sets ⋮ Bounds on the leaf number in graphs of girth 4 or 5 ⋮ Kernel Bounds for Path and Cycle Problems ⋮ A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6 ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Hardness and approximation results for black hole search in arbitrary networks ⋮ Bounds on domination parameters in graphs: a brief survey ⋮ Upper bounds for the total rainbow connection of graphs ⋮ Parameterized complexity of graph burning ⋮ Lower bounds on the number of leaves in spanning trees ⋮ Further results on the total monochromatic connectivity of graphs ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Robust Connectivity of Graphs on Surfaces ⋮ Some results on spanning trees ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ Hamiltonicity, minimum degree and leaf number ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Kernel bounds for path and cycle problems ⋮ Bounds of the number of leaves of spanning trees in graphs without triangles ⋮ Bounds of the number of leaves of spanning trees ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Spanning trees with few non-leaves ⋮ The number and average size of connected sets in graphs with degree constraints ⋮ Improved bounds for spanning trees with many leaves ⋮ Radius, leaf number, connected domination number and minimum degree ⋮ Spanning Trees and Domination in Hypercubes ⋮ Minimum Degree and Dominating Paths ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ Leaf number and Hamiltonian \(C_4\)-free graphs ⋮ Improved pyrotechnics: closer to the burning number conjecture ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ Graphs with forbidden subgraphs and leaf number ⋮ On graphs with few disjoint \(t\)-star minors ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ On spanning cycles, paths and trees ⋮ A new algorithm for finding trees with many leaves ⋮ Confronting intractability via parameters ⋮ Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Spanning paths in graphs ⋮ Spanning trees: A survey ⋮ Connected domination number of a graph and its complement ⋮ On minimum degree, leaf number, traceability and Hamiltonicity in graphs ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Spanning trees in graphs of minimum degree 4 or 5 ⋮ On the \(r\)-domination number of a graph ⋮ 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 ⋮ Constructing a spanning tree with many leaves ⋮ Leafy spanning trees in hypercubes ⋮ A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ 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 ⋮ Note on the vertex-rainbow index of a graph ⋮ Spanning trees with many leaves ⋮ Connected Domination ⋮ Lower bounds on the leaf number in graphs with forbidden subgraphs ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ A note on connected domination number and leaf number ⋮ Minimum degree, leaf number and traceability ⋮ Modifying a graph using vertex elimination

This page was built for publication: Spanning Trees with Many Leaves