Spanning spiders and light-splitting switches

DOI10.1016/J.DISC.2004.04.005zbMath1044.05048OpenAlexW1999323173MaRDI QIDQ1877652

Luisa Gargano, Ugo Vaccaro, Ladislav Stacho, Pavol Hell, Mikael Hammar

Publication date: 19 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.disc.2004.04.005

zbMATH Keywords

Hamilton pathSpanning treeBranch vertex

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Eulerian and Hamiltonian graphs (05C45)

Related Items (32)

The spanning k-trees, perfect matchings and spectral radius of graphs ⋮ On the terminal connection problem ⋮ An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices ⋮ Degree sums and spanning brooms of a graph ⋮ On finding spanning trees with few leaves ⋮ Degree Conditions for Spanning Brooms ⋮ On minimum leaf spanning trees and a criticality notion ⋮ On the computational difficulty of the terminal connection problem ⋮ Spider covers and their applications ⋮ Spanning trees whose stems are spiders ⋮ Spanning trees homeomorphic to a small tree ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Neighborhood unions and extremal spanning trees ⋮ Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty ⋮ Spanning trees with at most \(k\) leaves in \(K_{1,4}\)-free graphs ⋮ Leaf-Critical and Leaf-Stable Graphs ⋮ Spiders everywhere ⋮ Spanning trees: A survey ⋮ An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes ⋮ Depth first search in claw-free graphs ⋮ Spanning 5-ended trees in \(K_{1,5}\)-free graphs ⋮ Gallai's question and constructions of almost hypotraceable graphs ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ On spanning trees with few branch vertices ⋮ Spanning trees whose stems have a bounded number of branch vertices ⋮ Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free graphs ⋮ Spanning trees with a bounded number of branch vertices in a claw-free graph ⋮ Spanning trees with at most 6 leaves in \(K_{1,5}\)-free graphs ⋮ The distance spectral radius of graphs with given number of odd vertices ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Spanning Trees with Few Branch Vertices ⋮ Approximating spanning trees with few branches

Cites Work

• On approximating the longest path in a graph
• Planar cubic hypohamiltonian and hypotraceable graphs
• Maximal trees with bounded maximum degree in a graph
• Hypohamiltonian and hypotraceable graphs
• A note on Hamiltonian circuits
• Finding long paths and cycles in sparse Hamiltonian graphs
• Note on Hamilton Circuits
• Longest paths and cycles in K1,3-free graphs
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Hamiltonicity for K_{1, r}‐free graphs
• Some Theorems on Abstract Graphs
• A sufficient condition for a graph to have a \(k\)-tree
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Spanning spiders and light-splitting switches