On the Problem of Decomposing a Graph into n Connected Factors
From MaRDI portal
Publication:3275433
DOI10.1112/jlms/s1-36.1.221zbMath0096.38001OpenAlexW2058858486WikidataQ105584980 ScholiaQ105584980MaRDI QIDQ3275433
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.221
Related Items
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, Packing plane spanning trees and paths in complete geometric graphs, Vertex-coloring 3-edge-weighting of some graphs, Extensions of matroid covering and packing, Algorithms for detecting dependencies and rigid subsystems for CAD, On the \(s\)-hamiltonianicity of an hourglass-free line graph, A note on biased and non-biased games, Algorithms for finding a rooted \((k,1)\)-edge-connected orientation, On spanning disjoint paths in line graphs, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Linking (n-2)-dimensional panels in n-space. II: (n-2,2)-frameworks and body and Hinge structures, 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, Strengthened Ore conditions for \((s, t)\)-supereulerian graphs, Hitting time for \(k\) edge-disjoint spanning trees in a random graph, A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs, On reachability mixed arborescence packing, Packing arborescences in random digraphs, On the complexity of packing rainbow spanning trees, The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties, 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, Edge-disjoint spanning trees and eigenvalues of graphs, Packing plane spanning trees into a point set, Edge-disjoint spanning trees and eigenvalues, Antisymmetric flows and edge-connectivity, Arc-disjoint paths and trees in 2-regular digraphs, Decomposing graphs into paths of fixed length, On \(( s , t )\)-supereulerian graphs with linear degree bounds, A linking polynomial of two matroids, 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, Polynomially determine if a graph is \((s,3)\)-supereulerian, Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, Matching edges and faces in polygonal partitions, Collapsible subgraphs of a 4-edge-connected graph, 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, Blocking optimal structures, Steiner tree packing number and tree connectivity, Pebble game algorithms and sparse graphs, 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, The \(\lambda_3\)-connectivity and \(\kappa_3\)-connectivity of recursive circulants, Partitions of complete geometric graphs into plane trees, Arboricity and tree-packing in locally finite graphs, 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, Monochromatic \(k\)-edge-connection colorings of graphs, The characterization of sufficient visibility in the direct reference plane approach for multiple views with missing data, Spectral conditions for graph rigidity in the Euclidean plane, Edge vulnerability parameters of bisplit graphs, Rainbow monochromatic \(k\)-edge-connection colorings of graphs, The region smoothing swap game, Network strength games: the core and the nucleolus, Edge disjoint spanning trees in random graphs, Group connectivity and group coloring: small groups versus large groups, Graphs with forbidden subgraphs, 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, Complexity of some arc-partition problems for digraphs, Variations on a game, Connectivity and edge-disjoint spanning trees, On flows in bidirected graphs, The connectivity of acyclic orientation graphs, Bounds of the number of disjoint spanning trees, Spanning tree packing and 2-essential edge-connectivity, On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs, Contractible subgraphs in 3-connected graphs, All 4-connected line graphs of claw free graphs are Hamiltonian connected, 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, Network reinforcement, 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, On the first-order edge tenacity of a graph, Packing Steiner trees, Path-connectivity in graphs, 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, 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, Graph factors and factorization: 1985--2003: a survey, Generalized polymatroids and submodular flows, On the spanning tree polyhedron, Packing Steiner trees on four terminals, 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, Packing of rigid spanning subgraphs and spanning trees, On spanning tree packings of highly edge connected graphs, A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid, Edge-decomposition of graphs into copies of a tree with four edges, Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs, On graph thickness, geometric thickness, and separator theorems, On the orientation of graphs, 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, Some inequalities for the Tutte polynomial, 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, Constructive characterizations for packing and covering with trees, On decomposing a hypergraph into \(k\) connected sub-hypergraphs, Combined connectivity augmentation and orientation problems, Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs, Highly connected molecular graphs are rigid in three dimensions, Arc-disjoint spanning sub(di)graphs in digraphs, Flows and parity subgraphs of graphs with large odd-edge-connectivity, Spanning cycles in regular matroids without small cocircuits, Circular flow on signed graphs, Decomposing a graph into bistars, Compatible geometric matchings, The constructive characterization of \((k,l)\)-edge-connected digraphs, The complexity of controlled selection, On the tractability of some natural packing, covering and partitioning problems, Spanning trees: A survey, How many conjectures can you stand? A survey, Inapproximability and approximability of minimal tree routing and coloring, Faster algorithms for security games on matroids, Characterizations of strength extremal graphs, Forests, frames, and games: Algorithms for matroid sums and applications, On the higher-order edge toughness of a graph, Submodular functions in graph theory, 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, Heuristics for the central tree problem, 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, Group flow, complex flow, unit vector flow, and the \((2 + \epsilon)\)-flow conjecture, Branch-and-cut approaches for chance-constrained formulations of reliable network design problems, Bidirectional retracting-free double tracings and upper embeddability of graphs, 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, Sparse hypergraphs and pebble game algorithms, Sparsity-certifying graph decompositions, On the rigidity of molecular graphs, A network theory approach to the rigidity of skeletal structures. II: Laman's theorem and topological formulae, Rigidity of multi-graphs. I: Linking rigid bodies in n-space, On hamiltonian line graphs and connectivity, Label-connected graphs and the gossip problem, Unnamed Item, Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems, 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, Spanning Rigid Subgraph Packing and Sparse Subgraph Covering, Tree robustness of a graph, Unnamed Item, Good orientations of unions of edge‐disjoint spanning trees, 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, 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, Good acyclic orientations of 4‐regular 4‐connected graphs, 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, 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, FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs, Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs, Finding small complete subgraphs efficiently, Count and cofactor matroids of highly connected graphs, Homomorphisms to small negative even cycles, Unnamed Item, Blocking and anti-blocking pairs of polyhedra, Approximating Minimum Cost Connectivity Orientation and Augmentation, 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, 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, 4-edge-connected 4-regular maps on the projective plane, Fully dynamic MIS in uniformly sparse graphs, Fast and Deterministic Approximations for k-Cut., Transversal matroid intersections and related packings, Unnamed Item, Playing to Retain the Advantage, Connected (g, f)-factors, A new characterization of the maximum genus of a graph, Unnamed Item, On extremal graphs with exactly one Steiner tree connecting any $k$ vertices, Packing the Steiner trees of a graph, Orientations of infinite graphs with prescribed edge-connectivity, Unnamed Item, Generalized connectivity of some total graphs, A new integer programming formulation of the graphical traveling salesman problem, Fully dynamic arboricity maintenance, A new integer programming formulation of the graphical traveling salesman problem, Circular Flows in Planar Graphs, Decompositions of highly connected graphs into paths of length 3, Opposite Elements in Clutters, Unnamed Item, 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, Unnamed Item, Hamilton cycles in 6-connected claw-free graphs (Extended abstract), Playing to retain the advantage, Ons-Hamiltonian Line Graphs, An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs
