Indexed by:
Abstract:
A bisection of a graph G is a partition of its vertex set into two sets which differ in size by at most 1, and its size is the number of edges between the two sets. The Max-Bisection problem is to find a bisection of G maximizing its size. An (l,r)-fan is a graph on (r−1)l+1 vertices consisting of l cliques of order r that intersect in exactly one common vertex. Let G be a connected graph with n vertices, m edges, and minimum degree at least 2. In this paper, we show that if G contains neither K2,l nor (l,4)-fan, then G has a bisection of size at least m∕2+(n−l+1)∕4, which improves the result given by Jin and Xu. As a corollary, it implies that every connected graph with n vertices, m edges, and minimum degree at least 2 and without cycles of length 4 has a bisection of size at least m∕2+(n−1)∕4. This improves a result given by Fan, Hou and Yu. © 2019 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Mathematics
ISSN: 0012-365X
Year: 2020
Issue: 1
Volume: 343
0 . 8 7
JCR@2020
0 . 7 0 0
JCR@2023
ESI HC Threshold:50
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: