科研之友
微信
新浪微博
Facebook
分享链接
摘要
We solve the following problem: Can an undirected weighted graph G be partitioned into two nonempty 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 dG(x) = a(x) + b(x) + 2WG(x), for every vertex x, where dG(x), WG(x) are, respectively, the sum and maximum of incident edge weights.
- 出版日期2017-10
