Home>Results

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

[期刊论文]

A bound on judicious bipartitions of directed graphs

Share
Edit Delete 报错

author:

Hou, Jianfeng (Hou, Jianfeng.) [1] (Scholars:侯建锋) | Ma, Huawen (Ma, Huawen.) [2] | Yu, Xingxing (Yu, Xingxing.) [3] | Unfold

Indexed by:

Scopus SCIE CSCD

Abstract:

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received much attention lately. Scott (2005) asked the following natural question: What is the maximum constant c(d) such that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D) = V-1 ? V-2 satisfying min{e(V-1, V-2), e(V-2, V1)} > c(d)m? Here, for i = 1, 2, e(V-i, V3-i) denotes the number of arcs in D from V-i to V3-i. Lee et al. (2016) conjectured that every directed graph D with m arcs and minimum outdegree at least d > 2 admits a bipartition V(D) = V-1 ? V-2 such that minfe(V-1; V-2); e(V-2; V-1)g > (d 1 - 2(2d 1) + o(1)) m: In this paper, we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.

Keyword:

directed graph indegree outdegree partition tight component

Community:

  • [ 1 ] [Hou, Jianfeng]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350116, Peoples R China
  • [ 2 ] [Ma, Huawen]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350116, Peoples R China
  • [ 3 ] [Yu, Xingxing]Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
  • [ 4 ] [Zhang, Xia]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

Reprint 's Address:

  • [Yu, Xingxing]Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

Show more details

Version:

Related Article:

Source :

SCIENCE CHINA-MATHEMATICS

ISSN: 1674-7283

CN: 11-5837/O1

Year: 2020

Issue: 2

Volume: 63

Page: 297-308

1 . 3 3 1

JCR@2020

1 . 4 0 0

JCR@2023

ESI Discipline: MATHEMATICS;

ESI HC Threshold:50

JCR Journal Grade:2

CAS Journal Grade:2

Cited Count:

WoS CC Cited Count: 7

SCOPUS Cited Count: 6

30 Days PV: 0

Online/Total:57/10116050
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