Spanning trees: A survey
From MaRDI portal
Publication:659663
DOI10.1007/s00373-010-0973-2zbMath1232.05055OpenAlexW1966931974MaRDI QIDQ659663
Publication date: 24 January 2012
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-010-0973-2
Trees (05C05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Distance in graphs (05C12) Eulerian and Hamiltonian graphs (05C45)
Related Items (55)
Spanning trees with bounded degrees and leaves ⋮ Bounds on the leaf number in graphs of girth 4 or 5 ⋮ Degree sums and spanning brooms of a graph ⋮ Spanning trees and spanning closed walks with small degrees ⋮ Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below ⋮ Spanning trees with leaf distance at least \(d\) ⋮ Reoptimization of parameterized problems ⋮ Spanning \(k\)-ended trees of bipartite graphs ⋮ \(m\)-dominating \(k\)-ended trees of graphs ⋮ On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves ⋮ General variable neighborhood search for the minimum stretch spanning tree problem ⋮ Radius, leaf number, connected domination number and minimum degree ⋮ Minimum Degree and Dominating Paths ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ The number and degree distribution of spanning trees in the Tower of Hanoi graph ⋮ Spanning trees homeomorphic to a small tree ⋮ \(m\)-dominating \(k\)-trees of graphs ⋮ Completely independent spanning trees in line graphs ⋮ Rooted minors and locally spanning subgraphs ⋮ Representative families: a unified tradeoff-based approach ⋮ Progress on sufficient conditions for a graph to have a spanning \(k\)-ended tree ⋮ Edge-disjoint spanning trees and eigenvalues of regular graphs ⋮ Spanning trees with few peripheral branch vertices in a connected claw-free graph ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Spanning trees with at most \(k\) leaves in 2-connected \(K_{1 , r}\)-free graphs ⋮ A condition ensuring that a connected graph has a spanning tree with few leaves ⋮ Spectra of subdivision-vertex join and subdivision-edge join of two graphs ⋮ Spanning trees with small degrees and few leaves ⋮ Spanning 3-ended trees in \(k\)-connected \(K_{1,4}\)-free graphs ⋮ The minimum size of a graph with given tree connectivity ⋮ On specific factors in graphs ⋮ Spanning \(k\)-trees of bipartite graphs ⋮ Spanning trees with few peripheral branch vertices ⋮ A note on the independence number, connectivity and \(k\)-ended tree ⋮ Spanning paths and cycles in triangle-free graphs ⋮ Spanning trees with small diameters ⋮ Spanning trees of connected \(K_{1,t}\)-free graphs whose stems have a few leaves ⋮ Spanning 5-ended trees in \(K_{1,5}\)-free graphs ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ On spanning trees with few branch vertices ⋮ Game edge-connectivity of graphs ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Note on the spanning-tree packing number of lexicographic product graphs ⋮ Path-connectivity of lexicographic product graphs ⋮ Spanning trees whose reducible stems have a few branch vertices ⋮ Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free graphs ⋮ Spanning trees with at most 6 leaves in \(K_{1,5}\)-free graphs ⋮ Rainbow and properly colored spanning trees in edge-colored bipartite graphs ⋮ Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs ⋮ Spanning Trees with Few Branch Vertices ⋮ On the Power of Planned Infections in Networks ⋮ Counting spanning trees in self-similar networks by evaluating determinants ⋮ Spanning k-ended trees of 3-regular connected graphs ⋮ On the Hamiltonian property hierarchy of 3-connected planar graphs ⋮ A note on connected domination number and leaf number
Cites Work
- Edge-Disjoint Spanning Trees of Finite Graphs
- Interpolation theorem for diameters of spanning trees
- Hamiltonian results inK1,3-free graphs
- On the sum of all distances in a graph or digraph
- Spanning Trees with Many Leaves
- Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
- Spanning trees with leaf distance at least four
- Three tree-paths
- Approximation Algorithms for the Maximum Internal Spanning Tree Problem
- Sharp upper bounds for the number of spanning trees of a graph
- Edge disjoint Steiner trees in graphs without large bridges
- Optimal attack and reinforcement of a network
- On connectivities of tree graphs
- Vertex-disjoint paths and edge-disjoint branchings in directed graphs
- A lower bound on the number of spanning trees withk end-vertices
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
- Worst-Case Analysis of Network Design Problem Heuristics
- The complexity of the network design problem
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- Independence trees and Hamilton cycles
- On low bound of degree sequences of spanning trees inK-edge-connected graphs
- Broadcasting and Gossiping in de Bruijn Networks
- Maximizing spanning trees in almost complete graphs
- Connected Domination and Spanning Trees with Many Leaves
- Exact algorithms for minimum routing cost trees
- Disproof of a conjecture about independent branchings in k‐connected directed graphs
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- Average distance, minimum degree, and spanning trees
- Toughness, trees, and walks
- On the largest tree of given maximum degree in a connected graph
- The spanning trees forced by the path and the star
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Spanning Trees with Many Leaves in Regular Bipartite Graphs
- Parameterized Algorithms for Directed Maximum Leaf Problems
- 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
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Finding Four Independent Trees
- Nonseparating Planar Chains in 4-Connected Graphs
- Chain Decompositions of 4-Connected Graphs
- Trees in Polyhedral Graphs
- On the Recognition of Primes by Automata
- Polyhedral decompositions of cubic graphs
- On the existence of uniformly optimally reliable networks
- Spanning trees with many leaves
- On the spanning tree packing number of a graph: A survey
- A sufficient condition for a graph to have a \(k\)-tree
- Independent spanning trees with small depths in iterated line digraphs
- Spanning trees of bounded degree
- Spanning trees with constraints on the leaf degree
- Subforests of bipartite digraphs---the minimum degree condition
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees
- Toughness of \(K_{a,t}\)-minor-free graphs
- A spanning tree with high degree vertices
- Degree bounded spanning trees
- Spanning \(k\)-trees of \(n\)-connected graphs
- A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices
- On the higher-order edge toughness of a graph
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- Spanning trees with a bounded number of branch vertices in a claw-free graph
- Hamilton connected graphs
- On hamiltonian line graphs and connectivity
- On a \(k\)-tree containing specified leaves in a graph
- Further analysis of the number of spanning trees in circulant graphs
- Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
- Graph factors and factorization: 1985--2003: a survey
- An approximate max-Steiner-tree-packing min-Steiner-cut theorem
- 3-trees with few vertices of degree 3 in circuit graphs
- Edge-connectivity and edge-disjoint spanning trees
- Packing trees with constraints on the leaf degree
- A linear-time algorithm to compute a MAD tree of an interval graph
- Complexities of some interesting problems on spanning trees
- Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
- Variations of the maximum leaf spanning tree problem for bipartite graphs
- Bijections for Cayley trees, spanning trees, and their q-analogues
- On k-leaf-connected graphs
- A bound for the complexity of a simple graph
- The multi-tree approach to reliability in distributed networks
- On a connection between the existence of k-trees and the toughness of a graph
- Flows and generalized coloring theorems in graphs
- On a conjecture of Las Vergnas concerning certain spanning trees in graphs
- Panarboreal graphs
- Graphs with certain families of spanning trees
- Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
- Hamiltonism, degree sum and neighborhood intersections
- Spanning trees with bounded degrees
- Hamiltonian properties of graphs with large neighborhood unions
- Spanning trees in graphs of minimum degree 4 or 5
- On independent spanning trees
- Fractional arboricity, strength, and principal partitions in graphs and matroids
- Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
- A method in graph theory
- An upper bound for the number of spanning trees of a graph
- Maximal trees with bounded maximum degree in a graph
- The number of spanning trees of a complete multipartite graph
- Independent branchings in acyclic digraphs
- Independent trees and branchings in planar multigraphs
- The connectivities of leaf graphs of 2-connected graphs
- Laplacian matrices of graphs: A survey
- Trees in triangulations
- Independent trees in graphs
- Subtrees and subforests of graphs
- Spanning trees in locally planar triangulations
- A new technique for the characterization of graphs with a maximum number of spanning trees
- On spanning 2-trees in a graph
- The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)
- A note on matchings and spanning trees with bounded degrees
- Spanning trees with pairwise nonadjacent endvertices
- On the characterization of graphs with maximum number of spanning trees
- Edge-disjoint trees containing some given vertices in a graph
- The complexity of the locally connected spanning tree problem
- MAD trees and distance-hereditary graphs
- On a tree graph defined by a set of cycles
- On decomposing a hypergraph into \(k\) connected sub-hypergraphs
- Subgraphs of graphs on surfaces with high representativity
- Degree-preserving spanning trees in small-degree graphs
- Approximation algorithms for the shortest total path length spanning tree problem
- The number of spanning trees in circulant graphs
- On the chromatic number of tree graphs
- Connected factors in graphs -- a survey
- 3-trees in polyhedral maps
- Transversal numbers of uniform hypergraphs
- The number of spanning trees in odd valent circulant graphs
- Spanning spiders and light-splitting switches
- Nonhamiltonian triangulations with large connectivity and representativity
- Subtrees of bipartite digraphs---the minimum degree condition
- Not every 2-tough graph is Hamiltonian
- On finding spanning trees with few leaves
- Neighborhood unions and extremal spanning trees
- The Erdős-Sós conjecture for spiders
- Spanning trees with few leaves
- A sharp upper bound for the number of spanning trees of a graph
- On a spanning tree with specified leaves
- Toughness in graphs -- a survey
- A note on Hamiltonian circuits
- Tough graphs and Hamiltonian circuits.
- On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
- Degree conditions for forests in graphs
- Connected (g, f)-factors
- Spanning trees with many leaves in cubic graphs
- Packing the Steiner trees of a graph
- The independence number condition for the existence of a spanning f-tree
- Disjoint paths, planarizing cycles, and spanning walks
- Closure for spanning trees and distant area
- Note on Hamilton Circuits
- On maximal paths and circuits of graphs
- The Enumeration of Point Labelled Chromatic Graphs and Trees
- On the Problem of Decomposing a Graph into n Connected Factors
This page was built for publication: Spanning trees: A survey
