Edge-Disjoint Spanning Trees of Finite Graphs

DOI10.1112/jlms/s1-36.1.445zbMath0102.38805OpenAlexW2042706982WikidataQ29027917 ScholiaQ29027917MaRDI QIDQ3286077

C. St. J. A. Nash-Williams

Publication date: 1961

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/jlms/s1-36.1.445

zbMATH Keywords

topology

Related Items

On the first-order edge tenacity of a graph, Packing Steiner trees, Arboricity and bipartite subgraph listing algorithms, A note on edge-disjoint Hamilton cycles in line graphs, An inductive construction of minimally rigid body-hinge simple graphs, Balanced decompositions of a signed graph, Extended formulations for sparsity matroids, Fast approximation for computing the fractional arboricity and extraction of communities of a graph, Fractional spanning tree packing, forest covering and eigenvalues, Graphs with large generalized (edge-)connectivity, Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree, Decomposing highly edge-connected graphs into paths of any given length, Edge-packings of graphs and network reliability, Source location with rigidity and tree packing requirements, Efficient computation of implicit representations of sparse graphs, Planar graphs and poset dimension, On the spanning tree polyhedron, Packing Steiner trees on four terminals, On \(k\)-planar crossing numbers, The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests, On 1-Hamilton-connected claw-free graphs, Bounding tree-width via contraction on the projective plane and torus, Global maker-breaker games on sparse graphs, A minimum degree condition forcing complete graph immersion, Simple planar graph partition into three forests, Packing of rigid spanning subgraphs and spanning trees, On spanning tree packings of highly edge connected graphs, Edge-decomposition of graphs into copies of a tree with four edges, Ore's condition for completely independent spanning trees, Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs, On graph thickness, geometric thickness, and separator theorems, Cycle double covers and the semi-Kotzig frame, Hamilton cycles in 5-connected line graphs, On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices, Cyclic orderings and cyclic arboricity of matroids, A short proof of the tree-packing theorem, Edge-disjoint trees containing some given vertices in a graph, 2-linked graphs, Edge-disjoint spanning trees and eigenvalues of regular graphs, Spectral conditions for edge connectivity and packing spanning trees in multigraphs, Generic global rigidity of body-hinge frameworks, Supereulerian graphs with width \(s\) and \(s\)-collapsible graphs, Highly connected molecular graphs are rigid in three dimensions, Flows and parity subgraphs of graphs with large odd-edge-connectivity, Spanning cycles in regular matroids without small cocircuits, Antisymmetric flows and edge-connectivity, Circular flow on signed graphs, Colouring edges with many colours in cycles, Decomposing a graph into bistars, Compatible geometric matchings, Lusternik-Schnirelmann category for simplicial complexes, A linking polynomial of two matroids, On the tractability of some natural packing, covering and partitioning problems, Spanning trees: A survey, How many conjectures can you stand? A survey, Two packing problems on \(k\)-matroid trees, Planar orientations with low out-degree and compaction of adjacency matrices, Inapproximability and approximability of minimal tree routing and coloring, Linking \((n-2)\)-dimensional panels in \(n\)-space. I: \((k-1,k)\)-graphs and \((k-1,k)\)-frames, Faster algorithms for security games on matroids, Characterizations of strength extremal graphs, Periodic rigidity on a variable torus using inductive constructions, A faster algorithm for packing branchings in digraphs, Forests, frames, and games: Algorithms for matroid sums and applications, On the higher-order edge toughness of a graph, Pin-collinear body-and-pin frameworks and the molecular conjecture, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Brick partitions of graphs, Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties, A rooted-forest partition with uniform vertex demand, The generic rank of body-bar-and-hinge frameworks, Duality in graph families, Nowhere-zero 3-flows of highly connected graphs, Fractional arboricity, strength, and principal partitions in graphs and matroids, A proof of the molecular conjecture, Bounded direction-length frameworks, Edge-disjoint spanning trees and depth-first search, What is on his mind?, Locally finite graphs with ends: A topological approach. II: Applications, Characterization of removable elements with respect to having \(k\) disjoint bases in a matroid, On maximally distant spanning trees of a graph, Eisenberg-Gale markets: algorithms and game-theoretic properties, Covering planar graphs with forests, one having bounded maximum degree, Edge-disjoint branching in directed multigraphs, Branch-and-cut approaches for chance-constrained formulations of reliable network design problems, Covering weighted graphs by even subgraphs, On a packing problem for infinite graphs and independence spaces, Structural theorems for submodular functions, polymatroids and polymatroid intersections, On packing connectors, Bounds on path connectivity, Spanning subgraph with Eulerian components, Packing of Steiner trees and \(S\)-connectors in graphs, Edge-decompositions of highly connected graphs into paths, Random sampling and greedy sparsification for matroid optimization problems, Sparse hypergraphs and pebble game algorithms, On the rigidity of molecular graphs, Arboricity and complement of a graph, On hamiltonian line graphs and connectivity, Label-connected graphs and the gossip problem, A short proof of Nash-Williams' theorem for the arboricity of a graph, Edge homogeneous colorings, Unnamed Item, Fully Dynamic Matching in Bipartite Graphs, Packing plane spanning trees and paths in complete geometric graphs, Contact Graphs of Circular Arcs, Degree condition for completely independent spanning trees, Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems, On spanning disjoint paths in line graphs, Linking (n-2)-dimensional panels in n-space. II: (n-2,2)-frameworks and body and Hinge structures, Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs, NASH‐WILLIAMS’ THEOREM ON DECOMPOSING GRAPHS INTO FORESTS, Computing Weighted Strength and Applications to Partitioning, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, Finding Totally Independent Spanning Trees with Linear Integer Programming, Spanning Rigid Subgraph Packing and Sparse Subgraph Covering, Anti-Ramsey problems in complete bipartite graphs for \(t\) edge-disjoint rainbow spanning trees, Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph, Connectivity of orientations of 3-edge-connected graphs, Tree robustness of a graph, Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries, Proof-labeling schemes: broadcast, unicast and in between, Unnamed Item, Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules, Straight-line drawings of 1-planar graphs, On the computational complexity of ordered subgraph recognition, Edge‐decomposing graphs into coprime forests, The Hamiltonicity of essentially 9‐connected line graphs, Packing of spanning mixed arborescences, Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties, Group Connectivity, Strongly Z_m-Connectivity, and Edge Disjoint Spanning Trees, An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem, The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties, Unnamed Item, Infinitesimal Rigidity in Normed Planes, Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs, Unnamed Item, Topological complexity of graphic arrangements, Theory of Principal Partitions Revisited, Balancing connected colourings of graphs, Edge-disjoint Steiner trees and connectors in graphs, Edge connectivity, packing spanning trees, and eigenvalues of graphs, A convexity upper bound for the number of maximal bicliques of a bipartite graph, Decomposing graphs into paths of fixed length, Packing Arborescences in Random Digraphs, Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees, A linear programming approach to increasing the weight of all minimum spanning trees, Fully dynamic MIS in uniformly sparse graphs, Fast and Deterministic Approximations for k-Cut., Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, Matching edges and faces in polygonal partitions, On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph, Pebble game algorithms and sparse graphs, Arboricity and tree-packing in locally finite graphs, Unnamed Item, Playing to Retain the Advantage, Connected (g, f)-factors, Unnamed Item, Edge partitions of optimal 2-plane and 3-plane graphs, Unnamed Item, On extremal graphs with exactly one Steiner tree connecting any $k$ vertices, Packing the Steiner trees of a graph, An orientation theorem with parity conditions, Orientations of infinite graphs with prescribed edge-connectivity, The characterization of sufficient visibility in the direct reference plane approach for multiple views with missing data, Unnamed Item, Generalized connectivity of some total graphs, A new integer programming formulation of the graphical traveling salesman problem, Non-preemptive tree packing, Edge vulnerability parameters of bisplit graphs, Fully dynamic arboricity maintenance, Anti-Ramsey Problems for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles, Matchings, or Trees, A new integer programming formulation of the graphical traveling salesman problem, Non-preemptive tree packing, Circular Flows in Planar Graphs, Decompositions of highly connected graphs into paths of length 3, The point-arboricity of a graph, Opposite Elements in Clutters, Unnamed Item, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, Balancing two spanning trees, On Maximal Independent Arborescence Packing, Unnamed Item, On 1-sum flows in undirected graphs, Edge disjoint Steiner trees in graphs without large bridges, PARTITIONS OF COMPLETE BIPARTITE GEOMETRIC GRAPHS INTO PLANE PERFECT MATCHINGS, Generalized Ramsey theory for graphs. I: Diagonal numbers, Unnamed Item, Unnamed Item, The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs, On flows in bidirected graphs, Edge Partitions and Visibility Representations of 1-planar Graphs, Hamilton cycles in 6-connected claw-free graphs (Extended abstract), Playing to retain the advantage, On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs, Ons-Hamiltonian Line Graphs, Network reinforcement, One Brick at a Time: A Survey of Inductive Constructions in Rigidity Theory, An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs, On some arboricities in planar graphs, Modulo orientations with bounded out-degrees, Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2, Decomposing planar graphs into graphs with degree restrictions, Spectral radius and edge‐disjoint spanning trees, Supereulerian regular matroids without small cocircuits, Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees in All Graphs, Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs, Achromatic arboricity on complete graphs, Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings, Graph rigidity properties of Ramanujan graphs, Completely independent spanning trees in line graphs, The thickness of fan-planar graphs is at most three, Finding small complete subgraphs efficiently, Count and cofactor matroids of highly connected graphs, An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth, Homomorphisms to small negative even cycles, Distributed CONGEST Algorithms against Mobile Adversaries, Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs, Packing spanning trees in highly essentially connected graphs, Globally rigid powers of graphs, Homomorphism bounded classes of graphs, Edge vulnerability parameters of split graphs, Avoider-Enforcer games, Vertex-coloring 3-edge-weighting of some graphs, Extensions of matroid covering and packing, Decomposing 4-connected planar triangulations into two trees and one path, Algorithms for detecting dependencies and rigid subsystems for CAD, On the \(s\)-hamiltonianicity of an hourglass-free line graph, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, A note on biased and non-biased games, Sublinear-time distributed algorithms for detecting small cliques and even cycles, Separation of partition inequalities with terminals, Extremal graphs for a spectral inequality on edge-disjoint spanning trees, Completely independent spanning trees in \(k\)-th power of graphs, On two-connected subgraph polytopes, Strengthened Ore conditions for \((s, t)\)-supereulerian graphs, Hitting time for \(k\) edge-disjoint spanning trees in a random graph, \(\mathsf{NIC}\)-planar graphs, A Hamilton sufficient condition for completely independent spanning tree, Colouring planar graphs with bounded monochromatic components, A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs, On reachability mixed arborescence packing, \(\ell^1\) and \(\ell^\infty\) plane, Packing arborescences in random digraphs, The parity Hamiltonian cycle problem, Disjoint compatible geometric matchings, On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity, Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs, Circular flows via extended Tutte orientations, Sufficient conditions for protection routing in IP networks, Edge-disjoint spanning trees and eigenvalues of graphs, Packing plane spanning trees into a point set, Edge-disjoint spanning trees and eigenvalues, On \(( s , t )\)-supereulerian graphs with linear degree bounds, An analogue of Edmonds' branching theorem for infinite digraphs, Toughness in pseudo-random graphs, Connectivity for quantum graphs, Fast approximation of matroid packing and covering, The minimum size of a graph with given tree connectivity, Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number, Generalized arboricity of graphs with large girth, Matrix choosability, Polynomially determine if a graph is \((s,3)\)-supereulerian, Collapsible subgraphs of a 4-edge-connected graph, Graphs without proper subgraphs of minimum degree 3 and short cycles, Combinatorial rigidity of incidence systems and application to dictionary learning, An enhancement of Nash-Williams' theorem on edge arboricity of graphs, Decomposing highly connected graphs into paths of length five, Edge-disjoint spanning trees and the number of maximum state circles of a graph, Steiner tree packing number and tree connectivity, On the notion of generalized minor in topological network theory and matroids, Note on edge-disjoint spanning trees and eigenvalues, Every 3-connected essentially 10-connected line graph is Hamilton-connected, Graded sparse graphs and body-length-direction frameworks, The \(\lambda_3\)-connectivity and \(\kappa_3\)-connectivity of recursive circulants, Antiparallel \(d\)-stable traces and a stronger version of ore problem, Covering planar graphs with forests, Extremal infinite graph theory, Edge-disjoint spanning trees and forests of graphs, Game edge-connectivity of graphs, Subgraph polytopes and independence polytopes of count matroids, Monochromatic \(k\)-edge-connection colorings of graphs, Spectral conditions for graph rigidity in the Euclidean plane, Rainbow monochromatic \(k\)-edge-connection colorings of graphs, The region smoothing swap game, Network strength games: the core and the nucleolus, Shannon switching games without terminals. II, Assur decompositions of direction-length frameworks, Edge disjoint spanning trees in random graphs, Group connectivity and group coloring: small groups versus large groups, Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes, Applications of matroid partition to tree decomposition, An algorithm for packing connectors, Spanning tree packing number and eigenvalues of graphs with given girth, Covering projective planar graphs with three forests, Variations on a game, Connectivity and edge-disjoint spanning trees, Planar Ramsey graphs, Distributed backup placement, The connectivity of acyclic orientation graphs, Bounds of the number of disjoint spanning trees, Spanning tree packing and 2-essential edge-connectivity, On chromatic number and minimum cut, Contractible subgraphs in 3-connected graphs, All 4-connected line graphs of claw free graphs are Hamiltonian connected, I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs, Orientations and detachments of graphs with prescribed degrees and connectivity, Decomposition into two trees with orientation constraints, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Degree sequence realizations with given packing and covering of spanning trees, On some algorithmic aspects of hypergraphic matroids, Spanning trees and spanning Eulerian subgraphs with small degrees, Circular flow number of highly edge connected signed graphs, Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs, Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness, Globally balancing spanning trees, Inductive constructions for frameworks on a two-dimensional fixed torus