Decomposing Weighted Graphs

2017/02/01 by Amir Ban, Ban, Amir · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1702.00205

openalex publication_date 2017/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Partitions of multigraphs under degree constraints

Related

• Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted Graphs
• Losing Weight by Gaining Edges
• On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture
• On weighted sublinear separators
• On graphlike k-dissimilarity vectors