On minimum balanced bipartitions of triangle-free graphs
On minimum balanced bipartitions of triangle-free graphs
复制标题
关于无三角形图的最小平衡二分
DOI：
10.1007/s10878-012-9539-y
复制
发表时间：
2014-04
影响因子：
1
通讯作者：
许宝刚
中科院分区：
文献类型：
--
作者：
李海燕;Liang Yanting;刘木伙;许宝刚
图G的平衡二分划是将V（G）划分为两个子集V1和V2，这两个子集的基数相差至多1。G的一个最小平衡二分划是G的一个平衡二分划V1，V2 minimizinge（V1，V2），其中（V1，V2）是连接V1和V2的边数，通常称为二分划的大小。本文证明了：每一个2-连通图G都有一个平衡的二分图V1，V2，使得G的由V1和V2诱导的子图都是连通的。这产生了一个很好的上界的最小平衡二分割的稀疏图的大小。我们还提出了无三角形图的最小平衡二分划的大小的两个上界，这两个上界使Fan等人（Discrete Math.312：1077-1083，2012）的相应界变得尖锐。
Abalanced bipartitionof a graphGis a partition ofV(G) into two subsetsV1andV2that differ in cardinality by at most 1. Aminimum balanced bipartitionofGis a balanced bipartitionV1,V2ofGminimizinge(V1,V2), wheree(V1,V2) is the number of edges joiningV1andV2and is usually referred to as thesizeof the bipartition. In this paper, we show that every 2-connected graphGadmits a balanced bipartitionV1,V2such that the subgraphs ofGinduced byV1and byV2are both connected. This yields a good upper bound to the size of minimum balanced bipartition of sparse graphs. We also present two upper bounds to the size of minimum balanced bipartitions of triangle-free graphs which sharpen the corresponding bounds of Fan et al. (Discrete Math. 312:1077–1083, 2012).
登录
查看更多内容
DOI：
10.1016/j.jctb.2013.06.002
发表时间：
2011-09
期刊：
ArXiv
影响因子：
--
作者：
Choongbum Lee;Po-Shen Loh;B. Sudakov
通讯作者：
Choongbum Lee;Po-Shen Loh;B. Sudakov
DOI：
--
发表时间：
2002
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Marek Karpinski
通讯作者：
Marek Karpinski
DOI：
10.4018/978-1-5225-9380-5.ch014
发表时间：
2020
期刊：
Handbook of Research on Advanced Applications of Graph Theory in Modern Society
影响因子：
--
作者：
R. Seethalakshmi
通讯作者：
R. Seethalakshmi
DOI：
10.1016/j.disc.2011.11.030
发表时间：
2012-03
期刊：
Discret. Math.
影响因子：
--
作者：
G. Fan;Baogang Xu;Xingxing Yu;Chuixiang Zhou
通讯作者：
G. Fan;Baogang Xu;Xingxing Yu;Chuixiang Zhou
DOI：
10.1007/bf00337893
发表时间：
1987
期刊：
Order
影响因子：
--
作者：
通讯作者：
--