• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >On problems about judicious bipartitions of graphs
【24h】

On problems about judicious bipartitions of graphs

机译：论图表的明智双排问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Bollobas and Scott [5] conjectured that every graph G has a balanced bipartite spanning subgraph H such that for each v is an element of V (G), d(H) (v) >= (d(G)(v) - 1)/2. In this paper, we show that every graphic sequence has a realization for which this Bollobas-Scott conjecture holds, confirming a conjecture of Hartke and Seacrest [8]. On the other hand, we give an infinite family of counterexamples to this Bollobas-Scott conjecture, which indicates that ((d(G)(v) - 1)/2] (rather than (d(G)(v) - 1)/2) is probably the correct lower bound. We also study bipartitions V-1, V-2 of graphs with a fixed number of edges. We provide a (best possible) upper bound on e(V-1)(lambda) + e(V-2)(lambda) for any real lambda >= 1 (the case A = 2 is a question of Scott 12]) and answer a question of Scott (Problem 3.9 in [12]) on max{e(V-1), e(V-2)}. (C) 2019 Elsevier Inc. All rights reserved.
机译：Bollobas和Scott [5]介绍每个图G具有平衡二角形的跨越子图H，使得对于每个V的是V（g），d（h）（v）> =（d（g）（v）的元素 - 1）/ 2。 在本文中，我们表明每个图形序列都有一个这个Bollobas-Scott猜想所在的实现，确认HARTKE和SEACRETT的猜想[8]。 另一方面，我们向该Bollobas-Scott猜想中提供无限家庭的反应物，表明（（d（g）（v） - 1）/ 2]（而不是（d（g）（v） - 1 ）/ 2）可能是正确的下限。我们还研究了具有固定数量的边缘的图形V-1，V-2的图形。我们提供了（V-1）（Lambda）的（最佳）上限 任何真实λ的+ e（v-2）（lambda）> = 1（案例a = 2是scott 12的问题），并回答Max {e（ V-1），E（V-2）}。（c）2019年Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号