Indexed by:
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)≤m/k2 + k-1/2k2(2m+1/4-1/2)+2/3 for each i∈{1,2,...,k} and e(V1, . . . , Vk)≥k-1/k m+k-1/2k(2m+1/4-1/2)-(k-2)2/8k, where e(Vi) is the number of edges with both ends in Vi and e(V1,...,Vk)=m-σki=1 e(Vi). This partially solves a problem proposed by Bolloba's and Scott, and, for some values of m, solves the problem affirmatively. © 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Applied Mathematics
ISSN: 0166-218X
Year: 2014
Volume: 179
Page: 86-99
0 . 8 0 2
JCR@2014
1 . 0 0 0
JCR@2023
ESI HC Threshold:184
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 16
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: