Indexed by:
Abstract:
A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and it s size is the number of edges which go across the two parts. Let G be a graph with n vertices and m edges. Bollob & aacute;s and Scott asked the following: What are the largest and smallest cuts that we can guarantee with bisections of G? There are reasonable sufficient conditions such that G has bisections of size at least m/2 cn + for some c > 0. In this paper, we study the Min-Bisection problem which has arisen in numerous contexts, and initially give some sufficient conditions such that G has bisections of size at most m/2 - cn for some c > 0
Keyword:
Reprint 's Address:
Email:
Version:
Source :
JOURNAL OF GRAPH THEORY
ISSN: 0364-9024
Year: 2025
0 . 9 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: