Name
Abstract | ||
|---|---|---|
Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with m edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V1,…,Vk such that e(Vi)≤mk2+k−12k2(2m+14−12)+23 for each i∈{1,2,…,k} and e(V1,…,Vk)≥k−1km+k−12k(2m+14−12)−(k−2)28k, where e(Vi) is the number of edges with both ends in Vi and e(V1,…,Vk)=m−∑i=1ke(Vi). This partially solves a problem proposed by Bollobás and Scott, and, for some values of m, solves the problem affirmatively. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2014.07.002 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph,Max-Cut problem,Judicious partition,Switching | Partition problem,Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Partition (number theory),Maximum cut,Mathematics | Journal |
Volume | Issue | ISSN |
179 | C | 0166-218X |
Citations | PageRank | References |
7 | 0.56 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 7 | 0.56 |
| Jianfeng Hou | 2 | 10 | 2.65 |
| Qinghou Zeng | 3 | 7 | 1.57 |