• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Lin, Jing (Lin, Jing.) [1] | Zeng, Qinghou (Zeng, Qinghou.) [2] (Scholars:曾庆厚)

Indexed by:

SCIE

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. In this paper, motivated by several known results of Alon, Bollobas, Krivelevich and Sudakov about Max-Cut, we study maximum bisections of graphs without short even cycles. Let G be a graph on medges without cycles of length 4 and 6. We first extend a well-known result of Shearer on maximum cuts to bisections and show that if G has a perfect matching and degree sequence d(1), ..., d(n), then G admits a bisection of size at least m/2 + Omega (Sigma(n)(i=1) root d(i)). This is tight for certain polarity graphs. Together with a technique of Nikiforov, we prove that if G also contains no cycle of length 2k >= 6 then G either has a large bisection or is nearly bipartite. As a corollary, if G has a matching of size circle minus(n), then G admits a bisection of size at least m/2 + Omega (m((2k+1)/(2k+2)) and that this is tight for 2k is an element of {6, 10}; if G has a matching of size o(n), then the bound remains valid for Gwith minimum degree at least 2. (C) 2021 Elsevier Inc. All rights reserved.

Keyword:

Bipartition Bisection Even cycle Law of total probability

Community:

  • [ 1 ] [Lin, Jing]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
  • [ 2 ] [Zeng, Qinghou]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
  • [ 3 ] [Lin, Jing]Fujian Univ Technol, Sch Comp Sci & Math, Fuzhou 350118, Fujian, Peoples R China

Reprint 's Address:

  • 曾庆厚

    [Zeng, Qinghou]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMBINATORIAL THEORY SERIES A

ISSN: 0097-3165

Year: 2021

Volume: 180

1 . 2 6 3

JCR@2021

0 . 9 0 0

JCR@2023

ESI Discipline: MATHEMATICS;

ESI HC Threshold:36

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 6

SCOPUS Cited Count: 6

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:261/10373222
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1