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

Hamilton pathSpanning treeBranch vertex

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(43)

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

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)