Spanning trees: A survey (Q659663): Difference between revisions

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).

@@ Property / reviewed by @@
-Mikhail I. Ostrovskii
@@ Property / reviewed by: Mikhail I. Ostrovskii / rank @@
-Normal rank
@@ Property / reviewed by @@
+Mikhail I. Ostrovskii
@@ Property / reviewed by: Mikhail I. Ostrovskii / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00373-010-0973-2
+Normal rank
@@ Property / OpenAlex ID @@
+W1966931974
@@ Property / OpenAlex ID: W1966931974 / rank @@
+Normal rank
@@ Property / cites work @@
+Transversal numbers of uniform hypergraphs
@@ Property / cites work: Transversal numbers of uniform hypergraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms for Directed Maximum Leaf Problems
+Normal rank
@@ Property / cites work @@
+Better Algorithms and Bounds for Directed Maximum Leaf Problems
+Normal rank
@@ Property / cites work @@
+Nonhamiltonian triangulations with large connectivity and representativity
+Normal rank
@@ Property / cites work @@
+Further analysis of the number of spanning trees in circulant graphs
+Normal rank
@@ Property / cites work @@
+Maximal trees with bounded maximum degree in a graph
+Normal rank
@@ Property / cites work @@
+The Enumeration of Point Labelled Chromatic Graphs and Trees
+Normal rank
@@ Property / cites work @@
+Degree conditions for forests in graphs
@@ Property / cites work: Degree conditions for forests in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Trees in Polyhedral Graphs
@@ Property / cites work: Trees in Polyhedral Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+-trees in polyhedral maps
@@ Property / cites work: 3-trees in polyhedral maps / rank @@
+Normal rank
@@ Property / cites work @@
+Toughness in graphs -- a survey
@@ Property / cites work: Toughness in graphs -- a survey / rank @@
+Normal rank
@@ Property / cites work @@
+Not every 2-tough graph is Hamiltonian
@@ Property / cites work: Not every 2-tough graph is Hamiltonian / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian properties of graphs with large neighborhood unions
+Normal rank
@@ Property / cites work @@
+Broadcasting and Gossiping in de Bruijn Networks
@@ Property / cites work: Broadcasting and Gossiping in de Bruijn Networks / rank @@
+Normal rank
@@ Property / cites work @@
+On the existence of uniformly optimally reliable networks
+Normal rank
@@ Property / cites work @@
+Spanning trees with pairwise nonadjacent endvertices
+Normal rank
@@ Property / cites work @@
+A method in graph theory
@@ Property / cites work: A method in graph theory / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
+Normal rank
@@ Property / cites work @@
+Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
+Normal rank
@@ Property / cites work @@
+A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
+Normal rank
@@ Property / cites work @@
+Subtrees and subforests of graphs
@@ Property / cites work: Subtrees and subforests of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The spanning trees forced by the path and the star
+Normal rank
@@ Property / cites work @@
+Q4944739
@@ Property / cites work: Q4944739 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4374709
@@ Property / cites work: Q4374709 / rank @@
+Normal rank
@@ Property / cites work @@
+Independence trees and Hamilton cycles
@@ Property / cites work: Independence trees and Hamilton cycles / rank @@
+Normal rank
@@ Property / cites work @@
+On spanning 2-trees in a graph
@@ Property / cites work: On spanning 2-trees in a graph / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of the locally connected spanning tree problem
+Normal rank
@@ Property / cites work @@
+On the largest tree of given maximum degree in a connected graph
+Normal rank
@@ Property / cites work @@
+Connected Domination and Spanning Trees with Many Leaves
+Normal rank
@@ Property / cites work @@
+Fractional arboricity, strength, and principal partitions in graphs and matroids
+Normal rank
@@ Property / cites work @@
+Edge-connectivity and edge-disjoint spanning trees
+Normal rank
@@ Property / cites work @@
+Toughness of \(K_{a,t}\)-minor-free graphs
@@ Property / cites work: Toughness of \(K_{a,t}\)-minor-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the higher-order edge toughness of a graph
@@ Property / cites work: On the higher-order edge toughness of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q5284569
@@ Property / cites work: Q5284569 / rank @@
+Normal rank
@@ Property / cites work @@
+The number of spanning trees in odd valent circulant graphs
+Normal rank
@@ Property / cites work @@
+Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
+Normal rank
@@ Property / cites work @@
+Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
+Normal rank
@@ Property / cites work @@
+A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices
+Normal rank
@@ Property / cites work @@
+Tough graphs and Hamiltonian circuits.
@@ Property / cites work: Tough graphs and Hamiltonian circuits. / rank @@
+Normal rank
@@ Property / cites work @@
+A note on Hamiltonian circuits
@@ Property / cites work: A note on Hamiltonian circuits / rank @@
+Normal rank
@@ Property / cites work @@
+A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
+Normal rank
@@ Property / cites work @@
+Optimal attack and reinforcement of a network
@@ Property / cites work: Optimal attack and reinforcement of a network / rank @@
+Normal rank
@@ Property / cites work @@
+Chain Decompositions of 4-Connected Graphs
@@ Property / cites work: Chain Decompositions of 4-Connected Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Four Independent Trees
@@ Property / cites work: Finding Four Independent Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Nonseparating Planar Chains in 4-Connected Graphs
@@ Property / cites work: Nonseparating Planar Chains in 4-Connected Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees of bounded degree
@@ Property / cites work: Spanning trees of bounded degree / rank @@
+Normal rank
@@ Property / cites work @@
+MAD trees and distance-hereditary graphs
@@ Property / cites work: MAD trees and distance-hereditary graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm to compute a MAD tree of an interval graph
+Normal rank
@@ Property / cites work @@
+Average distance, minimum degree, and spanning trees
+Normal rank
@@ Property / cites work @@
+Degree-preserving spanning trees in small-degree graphs
+Normal rank
@@ Property / cites work @@
+A sharp upper bound for the number of spanning trees of a graph
+Normal rank
@@ Property / cites work @@
+Spanning trees with many leaves
@@ Property / cites work: Spanning trees with many leaves / rank @@
+Normal rank
@@ Property / cites work @@
+On a spanning tree with specified leaves
@@ Property / cites work: On a spanning tree with specified leaves / rank @@
+Normal rank
@@ Property / cites work @@
+A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees
+Normal rank
@@ Property / cites work @@
+Bijections for Cayley trees, spanning trees, and their q-analogues
+Normal rank
@@ Property / cites work @@
+Q4863427
@@ Property / cites work: Q4863427 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4390602
@@ Property / cites work: Q4390602 / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees in locally planar triangulations
@@ Property / cites work: Spanning trees in locally planar triangulations / rank @@
+Normal rank
@@ Property / cites work @@
+Connected (g, f)-factors
@@ Property / cites work: Connected (g, f)-factors / rank @@
+Normal rank
@@ Property / cites work @@
+Toughness, trees, and walks
@@ Property / cites work: Toughness, trees, and walks / rank @@
+Normal rank
@@ Property / cites work @@
+Q4649987
@@ Property / cites work: Q4649987 / rank @@
+Normal rank
@@ Property / cites work @@
+The independence number condition for the existence of a spanning f-tree
+Normal rank
@@ Property / cites work @@
+Q4351067
@@ Property / cites work: Q4351067 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4882555
@@ Property / cites work: Q4882555 / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs with certain families of spanning trees
@@ Property / cites work: Graphs with certain families of spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+On maximal paths and circuits of graphs
@@ Property / cites work: On maximal paths and circuits of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the chromatic number of tree graphs
@@ Property / cites work: On the chromatic number of tree graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Erdős-Sós conjecture for spiders
@@ Property / cites work: The Erdős-Sós conjecture for spiders / rank @@
+Normal rank
@@ Property / cites work @@
+Panarboreal graphs
@@ Property / cites work: Panarboreal graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Sharp upper bounds for the number of spanning trees of a graph
+Normal rank
@@ Property / cites work @@
+Exact algorithms for minimum routing cost trees
@@ Property / cites work: Exact algorithms for minimum routing cost trees / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonism, degree sum and neighborhood intersections
+Normal rank
@@ Property / cites work @@
+Neighborhood unions and extremal spanning trees
@@ Property / cites work: Neighborhood unions and extremal spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+On decomposing a hypergraph into \(k\) connected sub-hypergraphs
+Normal rank
@@ Property / cites work @@
+Degree bounded spanning trees
@@ Property / cites work: Degree bounded spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+Closure for spanning trees and distant area
@@ Property / cites work: Closure for spanning trees and distant area / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning Trees with Many Leaves in Regular Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4449221
@@ Property / cites work: Q4449221 / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning spiders and light-splitting switches
@@ Property / cites work: Spanning spiders and light-splitting switches / rank @@
+Normal rank
@@ Property / cites work @@
+Q4737170
@@ Property / cites work: Q4737170 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximizing spanning trees in almost complete graphs
+Normal rank
@@ Property / cites work @@
+Spanning trees with many leaves in cubic graphs
@@ Property / cites work: Spanning trees with many leaves in cubic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees in graphs of minimum degree 4 or 5
@@ Property / cites work: Spanning trees in graphs of minimum degree 4 or 5 / rank @@
+Normal rank
@@ Property / cites work @@
+An upper bound for the number of spanning trees of a graph
+Normal rank
@@ Property / cites work @@
+A bound for the complexity of a simple graph
@@ Property / cites work: A bound for the complexity of a simple graph / rank @@
+Normal rank
@@ Property / cites work @@
+On k-leaf-connected graphs
@@ Property / cites work: On k-leaf-connected graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Interpolation theorem for diameters of spanning trees
+Normal rank
@@ Property / cites work @@
+Independent spanning trees with small depths in iterated line digraphs
+Normal rank
@@ Property / cites work @@
+A lower bound on the number of spanning trees withk end-vertices
+Normal rank
@@ Property / cites work @@
+Independent trees in graphs
@@ Property / cites work: Independent trees in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Disproof of a conjecture about independent branchings in <i>k</i>‐connected directed graphs
+Normal rank
@@ Property / cites work @@
+Independent branchings in acyclic digraphs
@@ Property / cites work: Independent branchings in acyclic digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Independent trees and branchings in planar multigraphs
+Normal rank
@@ Property / cites work @@
+The multi-tree approach to reliability in distributed networks
+Normal rank
@@ Property / cites work @@
+Q4014627
@@ Property / cites work: Q4014627 / rank @@
+Normal rank
@@ Property / cites work @@
+Flows and generalized coloring theorems in graphs
@@ Property / cites work: Flows and generalized coloring theorems in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4471308
@@ Property / cites work: Q4471308 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of the network design problem
@@ Property / cites work: The complexity of the network design problem / rank @@
+Normal rank
@@ Property / cites work @@
+On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
+Normal rank
@@ Property / cites work @@
+Spanning trees with constraints on the leaf degree
+Normal rank
@@ Property / cites work @@
+Spanning trees with leaf distance at least four
@@ Property / cites work: Spanning trees with leaf distance at least four / rank @@
+Normal rank
@@ Property / cites work @@
+The connectivities of leaf graphs of 2-connected graphs
+Normal rank
@@ Property / cites work @@
+Q3433933
@@ Property / cites work: Q3433933 / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning \(k\)-trees of \(n\)-connected graphs
@@ Property / cites work: Spanning \(k\)-trees of \(n\)-connected graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4897473
@@ Property / cites work: Q4897473 / rank @@
+Normal rank
@@ Property / cites work @@
+Subgraphs of graphs on surfaces with high representativity
+Normal rank
@@ Property / cites work @@
+Q4894608
@@ Property / cites work: Q4894608 / rank @@
+Normal rank
@@ Property / cites work @@
+On independent spanning trees
@@ Property / cites work: On independent spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning Trees with Many Leaves
@@ Property / cites work: Spanning Trees with Many Leaves / rank @@
+Normal rank
@@ Property / cites work @@
+Connected factors in graphs -- a survey
@@ Property / cites work: Connected factors in graphs -- a survey / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-disjoint trees containing some given vertices in a graph
+Normal rank
@@ Property / cites work @@
+Edge disjoint Steiner trees in graphs without large bridges
+Normal rank
@@ Property / cites work @@
+A sufficient condition for a graph to have a \(k\)-tree
+Normal rank
@@ Property / cites work @@
+Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
+Normal rank
@@ Property / cites work @@
+An approximate max-Steiner-tree-packing min-Steiner-cut theorem
+Normal rank
@@ Property / cites work @@
+The number of spanning trees of a complete multipartite graph
+Normal rank
@@ Property / cites work @@
+On a tree graph defined by a set of cycles
@@ Property / cites work: On a tree graph defined by a set of cycles / rank @@
+Normal rank
@@ Property / cites work @@
+Variations of the maximum leaf spanning tree problem for bipartite graphs
+Normal rank
@@ Property / cites work @@
+Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
+Normal rank
@@ Property / cites work @@
+On connectivities of tree graphs
@@ Property / cites work: On connectivities of tree graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4411401
@@ Property / cites work: Q4411401 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Maximum Leaf Spanning Trees in Almost Linear Time
+Normal rank
@@ Property / cites work @@
+On a \(k\)-tree containing specified leaves in a graph
+Normal rank
@@ Property / cites work @@
+Spanning trees with a bounded number of branch vertices in a claw-free graph
+Normal rank
@@ Property / cites work @@
+Hamiltonian results inK1,3-free graphs
@@ Property / cites work: Hamiltonian results inK1,3-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Laplacian matrices of graphs: A survey
@@ Property / cites work: Laplacian matrices of graphs: A survey / rank @@
+Normal rank
@@ Property / cites work @@
+Q4232798
@@ Property / cites work: Q4232798 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5616724
@@ Property / cites work: Q5616724 / rank @@
+Normal rank
@@ Property / cites work @@
+-trees with few vertices of degree 3 in circuit graphs
+Normal rank
@@ Property / cites work @@
+Edge-Disjoint Spanning Trees of Finite Graphs
@@ Property / cites work: Edge-Disjoint Spanning Trees of Finite Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees with bounded degrees
@@ Property / cites work: Spanning trees with bounded degrees / rank @@
+Normal rank
@@ Property / cites work @@
+Note on Hamilton Circuits
@@ Property / cites work: Note on Hamilton Circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Hamilton connected graphs
@@ Property / cites work: Hamilton connected graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
+Normal rank
@@ Property / cites work @@
+A spanning tree with high degree vertices
@@ Property / cites work: A spanning tree with high degree vertices / rank @@
+Normal rank
@@ Property / cites work @@
+On the spanning tree packing number of a graph: A survey
+Normal rank
@@ Property / cites work @@
+On the characterization of graphs with maximum number of spanning trees
+Normal rank
@@ Property / cites work @@
+Q2716516
@@ Property / cites work: Q2716516 / rank @@
+Normal rank
@@ Property / cites work @@
+A new technique for the characterization of graphs with a maximum number of spanning trees
+Normal rank
@@ Property / cites work @@
+Packing the Steiner trees of a graph
@@ Property / cites work: Packing the Steiner trees of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+On the sum of all distances in a graph or digraph
@@ Property / cites work: On the sum of all distances in a graph or digraph / rank @@
+Normal rank
@@ Property / cites work @@
+Graph factors and factorization: 1985--2003: a survey
+Normal rank
@@ Property / cites work @@
+Complexities of some interesting problems on spanning trees
+Normal rank
@@ Property / cites work @@
+Q3139712
@@ Property / cites work: Q3139712 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on matchings and spanning trees with bounded degrees
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Maximum Internal Spanning Tree Problem
+Normal rank
@@ Property / cites work @@
+On finding spanning trees with few leaves
@@ Property / cites work: On finding spanning trees with few leaves / rank @@
+Normal rank
@@ Property / cites work @@
+Q2707974
@@ Property / cites work: Q2707974 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Recognition of Primes by Automata
@@ Property / cites work: On the Recognition of Primes by Automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q4252040
@@ Property / cites work: Q4252040 / rank @@
+Normal rank
@@ Property / cites work @@
+Packing trees with constraints on the leaf degree
@@ Property / cites work: Packing trees with constraints on the leaf degree / rank @@
+Normal rank
@@ Property / cites work @@
+Polyhedral decompositions of cubic graphs
@@ Property / cites work: Polyhedral decompositions of cubic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Trees in triangulations
@@ Property / cites work: Trees in triangulations / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees with few leaves
@@ Property / cites work: Spanning trees with few leaves / rank @@
+Normal rank
@@ Property / cites work @@
+On the Problem of Decomposing a Graph into <i>n</i>  Connected Factors
+Normal rank
@@ Property / cites work @@
+Q4869540
@@ Property / cites work: Q4869540 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex-disjoint paths and edge-disjoint branchings in directed graphs
+Normal rank
@@ Property / cites work @@
+Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
+Normal rank
@@ Property / cites work @@
+On a conjecture of Las Vergnas concerning certain spanning trees in graphs
+Normal rank
@@ Property / cites work @@
+On a connection between the existence of k-trees and the toughness of a graph
+Normal rank
@@ Property / cites work @@
+Worst-Case Analysis of Network Design Problem Heuristics
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the shortest total path length spanning tree problem
+Normal rank
@@ Property / cites work @@
+A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
+Normal rank
@@ Property / cites work @@
+The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)
+Normal rank
@@ Property / cites work @@
+Q5461441
@@ Property / cites work: Q5461441 / rank @@
+Normal rank
@@ Property / cites work @@
+Disjoint paths, planarizing cycles, and spanning walks
+Normal rank
@@ Property / cites work @@
+Three tree-paths
@@ Property / cites work: Three tree-paths / rank @@
+Normal rank
@@ Property / cites work @@
+On hamiltonian line graphs and connectivity
@@ Property / cites work: On hamiltonian line graphs and connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Q3788028
@@ Property / cites work: Q3788028 / rank @@
+Normal rank
@@ Property / cites work @@
+The number of spanning trees in circulant graphs
@@ Property / cites work: The number of spanning trees in circulant graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On low bound of degree sequences of spanning trees inK-edge-connected graphs
+Normal rank
@@ Property / cites work @@
+Subforests of bipartite digraphs---the minimum degree condition
+Normal rank
@@ Property / cites work @@
+Subtrees of bipartite digraphs---the minimum degree condition
+Normal rank

Spanning trees: A survey (Q659663): Difference between revisions

Latest revision as of 20:21, 4 July 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)