Spanning trees: A survey
From MaRDI portal
Publication:659663
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
(76)- 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
- Title not available (Why is no real title available?)
- 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)
