Spanning spiders and light-splitting switches

DOI10.1016/J.DISC.2004.04.005MaRDI QIDQ1877652zbMATH OpenOpenAlexFDO

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

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

Branch vertexHamilton pathSpanning tree

Mathematics Subject Classification ID

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

Recommendations

• Near-optimal light spanners
• Near-optimal light spanners
• Spanning trees whose stems are spiders
• Spanders: distributed spanning expanders
• Distributed Construction of Light Networks
• Spanning line configurations
• The configuration space of a spider
• Multipath spanners
• On the configuration space of a spider

Cites work

• A note on Hamiltonian circuits
• A sufficient condition for a graph to have a k-tree
• Finding long paths and cycles in sparse Hamiltonian graphs
• Hamiltonicity for K_{1, r}‐free graphs
• scientific article; zbMATH DE number 637321 (Why is no real title available?)
• scientific article; zbMATH DE number 2038756 (Why is no real title available?)
• scientific article; zbMATH DE number 2086635 (Why is no real title available?)
• scientific article; zbMATH DE number 1421019 (Why is no real title available?)
• scientific article; zbMATH DE number 3349867 (Why is no real title available?)
• Hypohamiltonian and hypotraceable graphs
• Longest paths and cycles in K1,3-free graphs
• Maximal trees with bounded maximum degree in a graph
• Note on Hamilton Circuits
• On approximating the longest path in a graph
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Planar cubic hypohamiltonian and hypotraceable graphs
• Some Theorems on Abstract Graphs

Cited in

(44)

• Depth first search in claw-free graphs
• Gallai's question and constructions of almost hypotraceable graphs
• Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs
• Spider covers and their applications
• Spanning 5-ended trees in \(K_{1,5}\)-free graphs
• Degree sums and spanning brooms of a graph
• On minimum leaf spanning trees and a criticality notion
• Spiders everywhere
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• On spanning trees with few branch vertices
• Spanning trees with at most 6 leaves in \(K_{1,5}\)-free graphs
• A multivariate analysis of the strict terminal connection problem
• Approximating spanning trees with few branches
• An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
• On finding spanning trees with few leaves
• Neighborhood unions and extremal spanning trees
• The distance spectral radius of graphs with given number of odd vertices
• Leaf-critical and leaf-stable graphs
• On non-traceable, non-hypotraceable, arachnoid graphs
• scientific article; zbMATH DE number 2038756 (Why is no real title available?)
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• Spanning Trees with Few Branch Vertices
• The spanning k-trees, perfect matchings and spectral radius of graphs
• Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free graphs
• On the computational difficulty of the terminal connection problem
• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• 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
• Degree conditions for spanning brooms
• Spanning trees with few branch vertices in \(K_{1,4}\)-free graphs
• Spanning trees: A survey
• Spanning k-trees and distance signless Laplacian spectral radius of graphs
• Spanning trees with at most \(5\) leaves and branch vertices in total of \(K_{1,5}\)-free graphs
• Ore-type conditions for existence of a jellyfish in a graph
• Spanning trees minimizing branching costs
• Spanning trees of \(K_{1,4}\)-free graphs with a bounded number of leaves and branch vertices
• Spanning trees with a bounded number of branch vertices in a \(K_{1,4}\)-free graph
• Spanning trees of claw-free graphs with few leaves and branch vertices
• Spanning trees whose stems have a bounded number of branch vertices
• Network fault costs based on minimum leaf spanning trees
• Spanning trees with a bounded number of branch vertices in a claw-free graph
• On the terminal connection problem
• Spanning trees whose stems are spiders
• Spanning trees homeomorphic to a small tree

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

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