Decomposing weighted graphs
From MaRDI portal
Abstract: We solve the following problem: Can an undirected weighted graph G be parti- tioned into two non-empty induced subgraphs satisfying minimum constraints for the sum of edge weights at vertices of each subgraph? We show that this is possible for all constraints a(x), b(x) satisfying d_G(x) >= a(x) + b(x) + 2W_G(x), for every vertex x, where d_G(x), W_G(x) are, respectively, the sum and maximum of incident edge weights.
Recommendations
- Minimum weight \(H\)-decompositions of graphs: the bipartite case
- Graph-Theoretic Concepts in Computer Science
- Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size
- Partitions of multigraphs under minimum degree constraints
- Partitioning a weighted tree into subtrees with weights in a given range
Cited in
(16)- Decomposing weighted digraphs into sums of chains
- Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
- Partitions of multigraphs under minimum degree constraints
- A generalization of Stiebitz-type results on graph decomposition
- Partitions of multigraphs without \(C_4\)
- Partitions of graphs and multigraphs under degree constraints
- A note on partitions of graphs under degree constraints
- Asymptotically almost every \(2r\)-regular graph has an internal partition
- Weighted skeletons and fixed-share decomposition
- On a conjecture of Schweser and Stiebitz
- On connected partition with degree constraints
- scientific article; zbMATH DE number 1279320 (Why is no real title available?)
- Equitable induced decompositions of twin graphs
- Minimum weight \(H\)-decompositions of graphs: the bipartite case
- Graph partitions under average degree constraint
- On partitions of edge-colored graphs under color degree constraints
This page was built for publication: Decomposing weighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5360887)
