• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >The Erdos-Posa property for edge-disjoint immersions in 4-edge-connected graphs
【24h】

The Erdos-Posa property for edge-disjoint immersions in 4-edge-connected graphs

机译：ERDOS-POSA属性用于4边连接图中的边缘不相交的沉浸区

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

摘要

A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdos-Posa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint K-t-immersions, or an edge subset F of size at most f(k,t) such that G-F has no K-t-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdos-Posa property. (C) 2018 Elsevier Inc. All rights reserved
机译：如果将H的顶点映射到G的不同顶点，则将图H浸没在图G中，并且H的边缘被映射到加入G的相应顶点的路径，以便路径是成对边缘的方式 -disjoint。 在本文中，我们表明ERDOS-POSA属性适用于在4边连接的图形中包装边缘不相交的KT沉浸位。 更确切地说，对于正整数K和T，存在恒定的f（k，t），使得4边缘连接的图形g具有k边缘脱节kt-沉浸，或大多数的尺寸的边缘子集f （k，t）使得GF没有KT浸渍。 在此语句中的4边缘连接是最佳的，在某种意义上，3边连接的图形没有ERDOS-POSA属性。 （c）2018 Elsevier Inc.保留所有权利

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号