Spanning trees: A survey
type: Item
instance of: scholarly article
title: Spanning trees: A survey
zbMATH Open document ID: 1232.05055
author: Kenta Ozeki
author: Tomoki Yamashita
published in: Graphs and Combinatorics
publication date: 2012-01-24T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5999810
zbMATH Keywords: Spanning tree
zbMATH Keywords: Hamiltonian cycle
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
full work available at URL: s00373-010-0973-2
OpenAlex ID: W1966931974
cites work: Transversal numbers of uniform hypergraphs
cites work: Parameterized Algorithms for Directed Maximum Leaf Problems
cites work: Better Algorithms and Bounds for Directed Maximum Leaf Problems
cites work: Nonhamiltonian triangulations with large connectivity and representativity
cites work: Further analysis of the number of spanning trees in circulant graphs
cites work: Maximal trees with bounded maximum degree in a graph
cites work: The Enumeration of Point Labelled Chromatic Graphs and Trees
cites work: Degree conditions for forests in graphs
cites work: Trees in Polyhedral Graphs
cites work: 3-trees in polyhedral maps
cites work: Toughness in graphs -- a survey
cites work: Not every 2-tough graph is Hamiltonian
cites work: Hamiltonian properties of graphs with large neighborhood unions
cites work: Broadcasting and Gossiping in de Bruijn Networks
cites work: On the existence of uniformly optimally reliable networks
cites work: Spanning trees with pairwise nonadjacent endvertices
cites work: A method in graph theory
cites work: Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
cites work: Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
cites work: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
cites work: Subtrees and subforests of graphs
cites work: The spanning trees forced by the path and the star
cites work: Q4944739
cites work: Q4374709
cites work: Independence trees and Hamilton cycles
cites work: On spanning 2-trees in a graph
cites work: The complexity of the locally connected spanning tree problem
cites work: On the largest tree of given maximum degree in a connected graph
cites work: Connected Domination and Spanning Trees with Many Leaves
cites work: Fractional arboricity, strength, and principal partitions in graphs and matroids
cites work: Edge-connectivity and edge-disjoint spanning trees
cites work: Toughness of \(K_{a,t}\)-minor-free graphs
cites work: On the higher-order edge toughness of a graph
cites work: Q5284569
cites work: The number of spanning trees in odd valent circulant graphs
cites work: Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
cites work: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
cites work: A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices
cites work: Tough graphs and Hamiltonian circuits.
cites work: A note on Hamiltonian circuits
cites work: A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
cites work: Optimal attack and reinforcement of a network
cites work: Chain Decompositions of 4-Connected Graphs
cites work: Finding Four Independent Trees
cites work: Nonseparating Planar Chains in 4-Connected Graphs
cites work: Spanning trees of bounded degree
cites work: MAD trees and distance-hereditary graphs
cites work: A linear-time algorithm to compute a MAD tree of an interval graph
cites work: Average distance, minimum degree, and spanning trees
cites work: Degree-preserving spanning trees in small-degree graphs
cites work: A sharp upper bound for the number of spanning trees of a graph
cites work: Spanning trees with many leaves
cites work: On a spanning tree with specified leaves
cites work: A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees
cites work: Bijections for Cayley trees, spanning trees, and their q-analogues
cites work: Q4863427
cites work: Q4390602
cites work: Spanning trees in locally planar triangulations
cites work: Connected \((g,f)\)-factors
cites work: Toughness, trees, and walks

Spanning trees: A survey (cites work)
cites work: Q4649987

Spanning trees: A survey (cites work)
cites work: The independence number condition for the existence of a spanning f-tree

Spanning trees: A survey (cites work)
cites work: Q4351067

Spanning trees: A survey (cites work)
cites work: Q4882555

Spanning trees: A survey (cites work)
cites work: Graphs with certain families of spanning trees

Spanning trees: A survey (cites work)
cites work: On maximal paths and circuits of graphs

Spanning trees: A survey (cites work)
cites work: On the chromatic number of tree graphs

Spanning trees: A survey (cites work)
cites work: The Erdős-Sós conjecture for spiders

Spanning trees: A survey (cites work)
cites work: Panarboreal graphs

Spanning trees: A survey (cites work)
cites work: Sharp upper bounds for the number of spanning trees of a graph

Spanning trees: A survey (cites work)
cites work: Exact algorithms for minimum routing cost trees

Spanning trees: A survey (cites work)
cites work: Hamiltonism, degree sum and neighborhood intersections

Spanning trees: A survey (cites work)
cites work: Neighborhood unions and extremal spanning trees

Spanning trees: A survey (cites work)
cites work: On decomposing a hypergraph into \(k\) connected sub-hypergraphs

Spanning trees: A survey (cites work)
cites work: Degree bounded spanning trees

Spanning trees: A survey (cites work)
cites work: Closure for spanning trees and distant area

Spanning trees: A survey (cites work)
cites work: Spanning Trees with Many Leaves in Regular Bipartite Graphs

Spanning trees: A survey (cites work)
cites work: Q4198056

Spanning trees: A survey (cites work)
cites work: Q4449221

Spanning trees: A survey (cites work)
cites work: Spanning spiders and light-splitting switches

Spanning trees: A survey (cites work)
cites work: Q4737170

Spanning trees: A survey (cites work)
cites work: Maximizing spanning trees in almost complete graphs

Spanning trees: A survey (cites work)
cites work: Spanning trees with many leaves in cubic graphs

Spanning trees: A survey (cites work)
cites work: Spanning trees in graphs of minimum degree 4 or 5

Spanning trees: A survey (cites work)
cites work: An upper bound for the number of spanning trees of a graph

Spanning trees: A survey (cites work)
cites work: A bound for the complexity of a simple graph

Spanning trees: A survey (cites work)
cites work: On k-leaf-connected graphs

Spanning trees: A survey (cites work)
cites work: Interpolation theorem for diameters of spanning trees

Spanning trees: A survey (cites work)
cites work: Independent spanning trees with small depths in iterated line digraphs

Spanning trees: A survey (cites work)
cites work: A lower bound on the number of spanning trees withk end-vertices

Spanning trees: A survey (cites work)
cites work: Independent trees in graphs

Spanning trees: A survey (cites work)
cites work: Disproof of a conjecture about independent branchings in k‐connected directed graphs

Spanning trees: A survey (cites work)
cites work: Independent branchings in acyclic digraphs

Spanning trees: A survey (cites work)
cites work: Independent trees and branchings in planar multigraphs

Spanning trees: A survey (cites work)
cites work: The multi-tree approach to reliability in distributed networks

Spanning trees: A survey (cites work)
cites work: Q4014627

Spanning trees: A survey (cites work)
cites work: Flows and generalized coloring theorems in graphs

Spanning trees: A survey (cites work)
cites work: Q4471308

Spanning trees: A survey (cites work)
cites work: The complexity of the network design problem

Spanning trees: A survey (cites work)
cites work: On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs

Spanning trees: A survey (cites work)
cites work: Spanning trees with constraints on the leaf degree

Spanning trees: A survey (cites work)
cites work: Spanning trees with leaf distance at least four

Spanning trees: A survey (cites work)
cites work: The connectivities of leaf graphs of 2-connected graphs

Spanning trees: A survey (cites work)
cites work: Q3433933

Spanning trees: A survey (cites work)
cites work: Spanning \(k\)-trees of \(n\)-connected graphs

Spanning trees: A survey (cites work)
cites work: Q4897473

Spanning trees: A survey (cites work)
cites work: Subgraphs of graphs on surfaces with high representativity

Spanning trees: A survey (cites work)
cites work: Q4894608

Spanning trees: A survey (cites work)
cites work: On independent spanning trees

Spanning trees: A survey (cites work)
cites work: Spanning Trees with Many Leaves

Spanning trees: A survey (cites work)
cites work: Connected factors in graphs -- a survey

Spanning trees: A survey (cites work)
cites work: Edge-disjoint trees containing some given vertices in a graph

Spanning trees: A survey (cites work)
cites work: Edge disjoint Steiner trees in graphs without large bridges

Spanning trees: A survey (cites work)
cites work: A sufficient condition for a graph to have a \(k\)-tree

Spanning trees: A survey (cites work)
cites work: Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs

Spanning trees: A survey (cites work)
cites work: An approximate max-Steiner-tree-packing min-Steiner-cut theorem

Spanning trees: A survey (cites work)
cites work: The number of spanning trees of a complete multipartite graph

Spanning trees: A survey (cites work)
cites work: On a tree graph defined by a set of cycles

Spanning trees: A survey (cites work)
cites work: Variations of the maximum leaf spanning tree problem for bipartite graphs

Spanning trees: A survey (cites work)
cites work: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

Spanning trees: A survey (cites work)
cites work: On connectivities of tree graphs

Spanning trees: A survey (cites work)
cites work: Q4411401

Spanning trees: A survey (cites work)
cites work: Approximating Maximum Leaf Spanning Trees in Almost Linear Time

Spanning trees: A survey (cites work)
cites work: On a \(k\)-tree containing specified leaves in a graph

Spanning trees: A survey (cites work)
cites work: Spanning trees with a bounded number of branch vertices in a claw-free graph

Spanning trees: A survey (cites work)
cites work: Hamiltonian results inK1,3-free graphs

Spanning trees: A survey (cites work)
cites work: Laplacian matrices of graphs: A survey

Spanning trees: A survey (cites work)
cites work: Q4232798

Spanning trees: A survey (cites work)
cites work: Q5616724

Spanning trees: A survey (cites work)
cites work: 3-trees with few vertices of degree 3 in circuit graphs

Spanning trees: A survey (cites work)
cites work: Edge-Disjoint Spanning Trees of Finite Graphs

Spanning trees: A survey (cites work)
cites work: Spanning trees with bounded degrees

Spanning trees: A survey (cites work)
cites work: Note on Hamilton Circuits

Spanning trees: A survey (cites work)
cites work: Hamilton connected graphs

Spanning trees: A survey (cites work)
cites work: Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs

Spanning trees: A survey (cites work)
cites work: A spanning tree with high degree vertices

Spanning trees: A survey (cites work)
cites work: On the spanning tree packing number of a graph: A survey

Spanning trees: A survey (cites work)
cites work: On the characterization of graphs with maximum number of spanning trees

Spanning trees: A survey (cites work)
cites work: Bounds on the maximum number of edge-disjoint Steiner trees of a graph

Spanning trees: A survey (cites work)
cites work: A new technique for the characterization of graphs with a maximum number of spanning trees

Spanning trees: A survey (cites work)
cites work: Packing the Steiner trees of a graph

Spanning trees: A survey (cites work)
cites work: On the sum of all distances in a graph or digraph

Spanning trees: A survey (cites work)
cites work: Graph factors and factorization: 1985--2003: a survey

Spanning trees: A survey (cites work)
cites work: Complexities of some interesting problems on spanning trees

Spanning trees: A survey (cites work)
cites work: Q3139712

Spanning trees: A survey (cites work)
cites work: A note on matchings and spanning trees with bounded degrees

Spanning trees: A survey (cites work)
cites work: Approximation Algorithms for the Maximum Internal Spanning Tree Problem

Spanning trees: A survey (cites work)
cites work: On finding spanning trees with few leaves

Spanning trees: A survey (cites work)
cites work: On spanning trees and walks of low maximum degree

Spanning trees: A survey (cites work)
cites work: On the Recognition of Primes by Automata

Spanning trees: A survey (cites work)
cites work: Q4252040

Spanning trees: A survey (cites work)
cites work: Packing trees with constraints on the leaf degree

Spanning trees: A survey (cites work)
cites work: Polyhedral decompositions of cubic graphs

Spanning trees: A survey (cites work)
cites work: Trees in triangulations

Spanning trees: A survey (cites work)
cites work: Spanning trees with few leaves

Spanning trees: A survey (cites work)
cites work: On the Problem of Decomposing a Graph into n Connected Factors

Spanning trees: A survey (cites work)
cites work: Q4869540

Spanning trees: A survey (cites work)
cites work: Vertex-disjoint paths and edge-disjoint branchings in directed graphs

Spanning trees: A survey (cites work)
cites work: Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen

Spanning trees: A survey (cites work)
cites work: On a conjecture of Las Vergnas concerning certain spanning trees in graphs

Spanning trees: A survey (cites work)
cites work: On a connection between the existence of k-trees and the toughness of a graph

Spanning trees: A survey (cites work)
cites work: Worst-Case Analysis of Network Design Problem Heuristics

Spanning trees: A survey (cites work)
cites work: Approximation algorithms for the shortest total path length spanning tree problem

Spanning trees: A survey (cites work)
cites work: A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees

Spanning trees: A survey (cites work)
cites work: The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)

Spanning trees: A survey (cites work)
cites work: Q5461441

Spanning trees: A survey (cites work)
cites work: Disjoint paths, planarizing cycles, and spanning walks

Spanning trees: A survey (cites work)
cites work: Three tree-paths

Spanning trees: A survey (cites work)
cites work: On hamiltonian line graphs and connectivity

Spanning trees: A survey (cites work)
cites work: Q3788028

Spanning trees: A survey (cites work)
cites work: The number of spanning trees in circulant graphs

Spanning trees: A survey (cites work)
cites work: On low bound of degree sequences of spanning trees inK-edge-connected graphs

Spanning trees: A survey (cites work)
cites work: Subforests of bipartite digraphs---the minimum degree condition

Spanning trees: A survey (cites work)
cites work: Subtrees of bipartite digraphs---the minimum degree condition

Spanning trees: A survey (DOI)
DOI: 10.1007/S00373-010-0973-2