Spanning trees with many leaves in cubic graphs

DOI10.1002/jgt.3190130604zbMath0693.05023OpenAlexW2048653445MaRDI QIDQ3035303

Aditya Shastri, Daniel J. Kleitman, Jerrold R. Griggs

Publication date: 1989

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: http://purl.umn.edu/4903

zbMATH Keywords

spanning treecubic graphmaximum number of leaves

Mathematics Subject Classification ID

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

Related Items (28)

Bounds on the leaf number in graphs of girth 4 or 5 ⋮ On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Lower bounds on the number of leaves in spanning trees ⋮ Robust Connectivity of Graphs on Surfaces ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Bounds of the number of leaves of spanning trees in graphs without triangles ⋮ Bounds of the number of leaves of spanning trees ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Spanning trees with few non-leaves ⋮ Improved bounds for spanning trees with many leaves ⋮ Radius, leaf number, connected domination number and minimum degree ⋮ Spanning Trees and Domination in Hypercubes ⋮ Average distance and connected domination ⋮ Graphs with forbidden subgraphs and leaf number ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Spanning paths in graphs ⋮ Spanning trees: A survey ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Spanning trees in graphs of minimum degree 4 or 5 ⋮ 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 ⋮ Connected Domination ⋮ Connected domination of regular graphs ⋮ 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

This page was built for publication: Spanning trees with many leaves in cubic graphs