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 in edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V-1, ... V-k such that e(V-i) <= m/k(2) + k-1/2k(2) (root 2m + 1/4 - 1/2) + 2/3 for each i is an element of {1, 2, ..., k} and e(V-1, ..., V-k) >= k-1/km + k-1/2k (root 2m + 1/4 - 1/2) - (k-2)(2)/8k, congruent to where e(V-i) is the number of edges with both ends in V-i and e (V-1, ..., V-k) = m - Sigma(k)(i=1) e(V-i). This partially solves a problem proposed by Bollobas and Scott, and, for some values of m, solves the problem affirmatively. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
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 Discipline: ENGINEERING;
ESI HC Threshold:184
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 14
SCOPUS Cited Count: 16
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: