Leafy spanning trees in hypercubes

DOI10.1016/S0893-9659(01)00047-7MaRDI QIDQ5950587zbMATH OpenOpenAlexFDO

Authors W. Duckworth, Paul E. Dunne, A. Gibbons, Michele Zito

Publication date 2 January 2002

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0893-9659(01)00047-7

zbMATH Keywords

leaves in trees of hypercubes

Mathematics Subject Classification ID

Trees (05C05)

Review text

A lower bound is found for the number of leaves of a spanning tree in a \(d\)-dimensional hypercube. This improves on the bound implied by a more general result of \textit{D. J. Kleitman} and \textit{D. B. West} [SIAM J. Discrete Math. 4, No. 1, 99-106 (1991; Zbl 0734.05041)].

Recommendations

• Spanning Trees and Domination in Hypercubes
• Spanning trees and domination in hypercubes
• Spanning subgraphs of a hypercube. IV: Rooted trees
• Spanning trees with many leaves in cubic graphs
• Spanning graphs of hypercubes: Starlike and double starlike trees

Cites work

• A short note on the approximability of the maximum leaves spanning tree problem
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 3318360 (Why is no real title available?)
• Independent domination in hypercubes
• Spanning Trees with Many Leaves

Cited in

(10)

• The starlike trees which span a hypercube
• Spanning subgraphs of a hypercube. IV: Rooted trees
• Spanning trees on hypercubic lattices and nonorientable surfaces
• Connectivity and edge-bipancyclicity of Hamming shell
• Regular connected bipancyclic spanning subgraphs of hypercubes
• Spanning Trees and Domination in Hypercubes
• Regular connected bipancyclic spanning subgraphs of torus networks
• Spanning trees and domination in hypercubes
• Leafy spanning arborescences in DAGs
• Leafy spanning arborescences in DAGs

This page was built for publication: Leafy spanning trees in hypercubes

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