CSpace  > 应用数学研究所
On bisections of directed graphs
Hou, Jianfeng1; Wu, Shufei1,2; Yan, Guiying3
2017-06-01
发表期刊EUROPEAN JOURNAL OF COMBINATORICS
ISSN0195-6698
卷号63页码:44-58
摘要A bisection of a graph is a partition of its vertex set into two sets which differ in size by at most 1. In this paper, we consider bisections of directed graphs such that both directions of the directed cuts contain many arcs. Let D be a directed graph with minimum outdegree delta >= 2 and m arcs. We show that if delta is even, then D has a bisection V(D) = V-1 boolean OR V-2 such that min{e(V-1, V-2),e(V-2, V-1)} > (delta/4(delta+1) + o(1))m, where e(V-i, V-j) denotes the number of arcs of D from V-i to V-j 10 for i not equal j and i,j = 1,2. If the underlying graph of D does not contain cycles of length 4, then we show that D admits a bisection V(D) = V-1 boolean OR V-2 such that minfe(V-1, V-2), e(V-2, V-1)} >= (1/4 + o(1))m. (C) 2017 Elsevier Ltd. All rights reserved.
DOI10.1016/j.ejc.2017.02.004
语种英语
资助项目National Natural Science Foundation of China[11331003] ; National Natural Science Foundation of China[11671087] ; National Natural Science Foundation of China[11631014] ; New Century Support Program of Fujian Province[JA14028]
WOS研究方向Mathematics
WOS类目Mathematics
WOS记录号WOS:000402344100004
出版者ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
引用统计
文献类型期刊论文
条目标识符http://ir.amss.ac.cn/handle/2S8OKBNM/25576
专题应用数学研究所
通讯作者Wu, Shufei
作者单位1.Fuzhou Univ, Ctr Discrete Math, Fujian 350003, Peoples R China
2.Henan Polytech Univ, Sch Math & Informat Sci, Jiaozuo 454000, Henan, Peoples R China
3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China
推荐引用方式
GB/T 7714
Hou, Jianfeng,Wu, Shufei,Yan, Guiying. On bisections of directed graphs[J]. EUROPEAN JOURNAL OF COMBINATORICS,2017,63:44-58.
APA Hou, Jianfeng,Wu, Shufei,&Yan, Guiying.(2017).On bisections of directed graphs.EUROPEAN JOURNAL OF COMBINATORICS,63,44-58.
MLA Hou, Jianfeng,et al."On bisections of directed graphs".EUROPEAN JOURNAL OF COMBINATORICS 63(2017):44-58.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Hou, Jianfeng]的文章
[Wu, Shufei]的文章
[Yan, Guiying]的文章
百度学术
百度学术中相似的文章
[Hou, Jianfeng]的文章
[Wu, Shufei]的文章
[Yan, Guiying]的文章
必应学术
必应学术中相似的文章
[Hou, Jianfeng]的文章
[Wu, Shufei]的文章
[Yan, Guiying]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。