Spanning trees: A survey
From MaRDI portal
Publication:659663
This survey does not contain any proofs, only definitions, statements of known results and related open problems, and 195 references. Considered types of spanning trees: with upper bounds on degrees, with upper bounds on the number of leaves or on the number of branch vertices, with small average distance, preserving degrees of as many vertices as possible, isomorphic to a particular tree (and some other, with more complicated descriptions).
Recommendations
Cites work
- 3-trees in polyhedral maps
- 3-trees with few vertices of degree 3 in circuit graphs
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
- A bound for the complexity of a simple graph
- A linear-time algorithm to compute a MAD tree of an interval graph
- A lower bound on the number of spanning trees withk end-vertices
- A method in graph theory
- A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees
- A new technique for the characterization of graphs with a maximum number of spanning trees
- A note on Hamiltonian circuits
- A note on matchings and spanning trees with bounded degrees
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- A sharp upper bound for the number of spanning trees of a graph
- A spanning tree of the 2^ m-dimensional hypercube with maximum number of degree-preserving vertices
- A spanning tree with high degree vertices
- A sufficient condition for a graph to have a k-tree
- An approximate max-Steiner-tree-packing min-Steiner-cut theorem
- An upper bound for the number of spanning trees of a graph
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- Approximation Algorithms for the Maximum Internal Spanning Tree Problem
- Approximation algorithms for the shortest total path length spanning tree problem
- Average distance, minimum degree, and spanning trees
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Bijections for Cayley trees, spanning trees, and their q-analogues
- Bounds on the maximum number of edge-disjoint Steiner trees of a graph
- Broadcasting and Gossiping in de Bruijn Networks
- Chain Decompositions of 4-Connected Graphs
- Closure for spanning trees and distant area
- Complexities of some interesting problems on spanning trees
- Connected (g,f)-factors
- Connected Domination and Spanning Trees with Many Leaves
- Connected factors in graphs -- a survey
- Degree bounded spanning trees
- Degree conditions for forests in graphs
- Degree-preserving spanning trees in small-degree graphs
- Disjoint paths, planarizing cycles, and spanning walks
- Disproof of a conjecture about independent branchings in k‐connected directed graphs
- Edge disjoint Steiner trees in graphs without large bridges
- Edge-connectivity and edge-disjoint spanning trees
- Edge-Disjoint Spanning Trees of Finite Graphs
- Edge-disjoint trees containing some given vertices in a graph
- Exact algorithms for minimum routing cost trees
- Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
- Finding Four Independent Trees
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
- Flows and generalized coloring theorems in graphs
- Fractional arboricity, strength, and principal partitions in graphs and matroids
- Further analysis of the number of spanning trees in circulant graphs
- Graph factors and factorization: 1985--2003: a survey
- Graphs with certain families of spanning trees
- Hamilton connected graphs
- Hamiltonian properties of graphs with large neighborhood unions
- Hamiltonian results inK1,3-free graphs
- Hamiltonism, degree sum and neighborhood intersections
- scientific article; zbMATH DE number 434863 (Why is no real title available?)
- scientific article; zbMATH DE number 5145367 (Why is no real title available?)
- scientific article; zbMATH DE number 4051653 (Why is no real title available?)
- scientific article; zbMATH DE number 68918 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1262807 (Why is no real title available?)
- scientific article; zbMATH DE number 1305098 (Why is no real title available?)
- scientific article; zbMATH DE number 1052827 (Why is no real title available?)
- scientific article; zbMATH DE number 1109399 (Why is no real title available?)
- scientific article; zbMATH DE number 1156578 (Why is no real title available?)
- scientific article; zbMATH DE number 1947432 (Why is no real title available?)
- scientific article; zbMATH DE number 2038756 (Why is no real title available?)
- scientific article; zbMATH DE number 2079349 (Why is no real title available?)
- scientific article; zbMATH DE number 2086635 (Why is no real title available?)
- scientific article; zbMATH DE number 841581 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 890671 (Why is no real title available?)
- scientific article; zbMATH DE number 932184 (Why is no real title available?)
- scientific article; zbMATH DE number 1420489 (Why is no real title available?)
- scientific article; zbMATH DE number 969101 (Why is no real title available?)
- scientific article; zbMATH DE number 2188342 (Why is no real title available?)
- scientific article; zbMATH DE number 3340110 (Why is no real title available?)
- Independence trees and Hamilton cycles
- Independent branchings in acyclic digraphs
- Independent spanning trees with small depths in iterated line digraphs
- Independent trees and branchings in planar multigraphs
- Independent trees in graphs
- Interpolation theorem for diameters of spanning trees
- Laplacian matrices of graphs: A survey
- Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
- MAD trees and distance-hereditary graphs
- Maximal trees with bounded maximum degree in a graph
- Maximizing spanning trees in almost complete graphs
- Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
- Neighborhood unions and extremal spanning trees
- Nonhamiltonian triangulations with large connectivity and representativity
- Nonseparating Planar Chains in 4-Connected Graphs
- Not every 2-tough graph is Hamiltonian
- Note on Hamilton Circuits
- On a k-tree containing specified leaves in a graph
- On a conjecture of Las Vergnas concerning certain spanning trees in graphs
- On a connection between the existence of k-trees and the toughness of a graph
- On a spanning tree with specified leaves
- On a tree graph defined by a set of cycles
- On connectivities of tree graphs
- On decomposing a hypergraph into \(k\) connected sub-hypergraphs
- On finding spanning trees with few leaves
- On hamiltonian line graphs and connectivity
- On independent spanning trees
- On k-leaf-connected graphs
- On low bound of degree sequences of spanning trees inK-edge-connected graphs
- On maximal paths and circuits of graphs
- On spanning 2-trees in a graph
- On spanning trees and walks of low maximum degree
- On the characterization of graphs with maximum number of spanning trees
- On the chromatic number of tree graphs
- On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
- On the existence of uniformly optimally reliable networks
- On the higher-order edge toughness of a graph
- On the largest tree of given maximum degree in a connected graph
- On the Problem of Decomposing a Graph into n Connected Factors
- On the Recognition of Primes by Automata
- On the spanning tree packing number of a graph: A survey
- On the sum of all distances in a graph or digraph
- Optimal attack and reinforcement of a network
- Packing the Steiner trees of a graph
- Packing trees with constraints on the leaf degree
- Panarboreal graphs
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Polyhedral decompositions of cubic graphs
- Sharp upper bounds for the number of spanning trees of a graph
- Spanning \(k\)-trees of \(n\)-connected graphs
- Spanning spiders and light-splitting switches
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- Spanning trees in graphs of minimum degree 4 or 5
- Spanning trees in locally planar triangulations
- Spanning trees of bounded degree
- Spanning trees with a bounded number of branch vertices in a claw-free graph
- Spanning trees with a bounded number of leaves in a claw-free graph.
- Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
- Spanning trees with bounded degrees
- Spanning trees with bounded total excess.
- Spanning trees with constraints on the leaf degree
- Spanning trees with few leaves
- Spanning trees with leaf distance at least four
- Spanning trees with many leaves
- Spanning Trees with Many Leaves
- Spanning trees with many leaves in cubic graphs
- Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
- Spanning Trees with Many Leaves in Regular Bipartite Graphs
- Spanning trees with pairwise nonadjacent endvertices
- Subforests of bipartite digraphs---the minimum degree condition
- Subgraphs of graphs on surfaces with high representativity
- Subtrees and subforests of graphs
- Subtrees of bipartite digraphs---the minimum degree condition
- The complexity of the locally connected spanning tree problem
- The complexity of the network design problem
- The connectivities of leaf graphs of 2-connected graphs
- The Enumeration of Point Labelled Chromatic Graphs and Trees
- The Erdős-Sós conjecture for spiders
- The independence number condition for the existence of a spanning f-tree
- The multi-tree approach to reliability in distributed networks
- The number of spanning trees in circulant graphs
- The number of spanning trees in odd valent circulant graphs
- The number of spanning trees of a complete multipartite graph
- The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)
- The spanning trees forced by the path and the star
- Three tree-paths
- Tough graphs and Hamiltonian circuits.
- Toughness in graphs -- a survey
- Toughness of \(K_{a,t}\)-minor-free graphs
- Toughness, trees, and walks
- Transversal numbers of uniform hypergraphs
- Trees in Polyhedral Graphs
- Trees in triangulations
- Variations of the maximum leaf spanning tree problem for bipartite graphs
- Vertex-disjoint paths and edge-disjoint branchings in directed graphs
- Worst-Case Analysis of Network Design Problem Heuristics
Cited in
(75)- Spectra of subdivision-vertex join and subdivision-edge join of two graphs
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- 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
- Game edge-connectivity of graphs
- Rainbow and properly colored spanning trees in edge-colored bipartite graphs
- Emerging spanning trees in the work of Candilis-Josic-Woods
- On the Hamiltonian property hierarchy of 3-connected planar graphs
- A note on connected domination number and leaf number
- Degree sums and spanning brooms of a graph
- Spanning trees and spanning closed walks with small degrees
- Reoptimization of parameterized problems
- The minimum size of a graph with given tree connectivity
- On specific factors in graphs
- Spanning trees with few peripheral branch vertices
- A note on the independence number, connectivity and \(k\)-ended tree
- On spanning trees with few branch vertices
- Spanning trees with at most 6 leaves in \(K_{1,5}\)-free graphs
- Spanning trees with leaf distance at least \(d\)
- Neighborhood unions and extremal spanning trees
- Note on the spanning-tree packing number of lexicographic product 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
- Spanning trees with bounded degrees and leaves
- Extension of spanning tree and applications
- Path-connectivity of lexicographic product graphs
- Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs.
- Counting spanning trees in self-similar networks by evaluating determinants
- Minimum degree and dominating paths
- How to Use Spanning Trees to Navigate in Graphs
- Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
- Spanning \(k\)-ended trees of bipartite graphs
- m-dominating k-ended trees of graphs
- Edge-disjoint spanning trees and eigenvalues of regular graphs
- Spanning trees with small degrees and few leaves
- scientific article; zbMATH DE number 742889 (Why is no real title available?)
- Spanning 3-ended trees in \(k\)-connected \(K_{1,4}\)-free graphs
- Spanning \(k\)-trees of bipartite graphs
- scientific article; zbMATH DE number 1424297 (Why is no real title available?)
- Spanning trees whose reducible stems have a few branch vertices.
- On the Power of Planned Infections in Networks
- Spanning k-ended trees of 3-regular connected graphs
- Bounds on the leaf number in graphs of girth 4 or 5
- A Survey on Spanning Tree Congestion
- Spanning paths and cycles in triangle-free graphs
- Spanning trees with small diameters
- Spanning Trees with Few Branch Vertices
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
- Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free 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
- Completely independent spanning trees in line graphs
- Rooted minors and locally spanning subgraphs
- Progress on sufficient conditions for a graph to have a spanning \(k\)-ended tree
- Degree conditions for spanning brooms
- Spanning trees with few branch vertices in \(K_{1,4}\)-free graphs
- The number of spanning trees for Sierpiński graphs and data center networks
- Strongly proper connected coloring of graphs
- Ore-type conditions for existence of a jellyfish in a graph
- On the eccentric distance sums of trees with fixed number of pendant paths
- On a conjecture by Griggs, Kleitman and Shastri
- Toward Grünbaum's conjecture
- Toward Grünbaum's conjecture bounding vertices of degree 4
- Spanning trees with few branch vertices in a chair-free graph. Independence number and degree sum conditions
- Sufficient conditions for k-factors and spanning trees of graphs
- Sufficient conditions for spanning trees with constrained leaf distance in a graph
- Sufficient conditions for k-factor-critical graphs and spanning k-trees of graphs
- Deeper local search for parameterized and approximation algorithms for maximum 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
- Representative families: a unified tradeoff-based approach
This page was built for publication: Spanning trees: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659663)
