Constructing full spanning trees for cubic graphs

DOI10.1016/0020-0190(81)90141-1MaRDI QIDQ1162518zbMATH OpenOpenAlexFDO

Authors James A. Storer

Publication date 1981

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(81)90141-1

zbMATH Keywords

NP-completespanning treemaximum leaf problem

Mathematics Subject Classification ID

Trees (05C05)

Cited in

(34)

• A note on connected domination number and leaf number
• Spanning paths in graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Minimum degree, leaf number and traceability.
• Spanning trees with many leaves
• Spanning trees in graphs of minimum degree 4 or 5
• Spanning Trees and Domination in Hypercubes
• On finding directed trees with many leaves
• Robust connectivity of graphs on surfaces
• Constructing a spanning tree with many leaves
• A Simple 2-Approximation for Maximum-Leaf Spanning Tree
• 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
• Flow-based formulation for the maximum leaf spanning tree problem
• Spanning trees with many leaves
• Bounds on the leaf number in graphs of girth 4 or 5
• Bounds of the number of leaves of spanning trees in graphs without triangles
• Connected domination of regular graphs
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Lower bounds on the number of leaves in spanning trees
• A 3-approximation algorithm for the maximum leaf \(k\)-forest problem
• Lower bounds on the leaf number in graphs with forbidden subgraphs
• An exact algorithm for the maximum leaf spanning tree problem.
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• Bounds of the number of leaves of spanning trees
• Radius, leaf number, connected domination number and minimum degree
• Leaf number and Hamiltonian \(C_4\)-free graphs
• Spanning Trees with Many Leaves in Regular Bipartite Graphs
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• Complexities of some interesting problems on spanning trees
• Connected domination
• Variations of the maximum leaf spanning tree problem for bipartite graphs
• Spanning trees with few non-leaves
• Graphs with forbidden subgraphs and leaf number

This page was built for publication: Constructing full spanning trees for cubic graphs

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