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 its size is the number of edges which go across the two parts. Let (Formula presented.) be a graph with (Formula presented.) vertices and (Formula presented.) edges. Bollobás and Scott asked the following: What are the largest and smallest cuts that we can guarantee with bisections of (Formula presented.) ? There are reasonable sufficient conditions such that (Formula presented.) has bisections of size at least (Formula presented.) for some (Formula presented.). In this paper, we study the Min-Bisection problem which has arisen in numerous contexts, and initially give some sufficient conditions such that (Formula presented.) has bisections of size at most (Formula presented.) for some (Formula presented.). © 2025 Wiley Periodicals LLC.
Keyword:
Reprint 's Address:
Email:
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: