...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >COMBINED DEGREE AND CONNECTIVITY CONDITIONS FOR H-LINKED GRAPHS
【24h】

COMBINED DEGREE AND CONNECTIVITY CONDITIONS FOR H-LINKED GRAPHS

机译：H联结图的组合度和连通性条件

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

摘要

For a given multigraph H, a graph G is H-linked if vertical bar G vertical bar >= vertical bar H vertical bar and for every injective map tau : V (H) -> V (G), we can find internally disjoint paths in G, such that every edge from uv in H corresponds to a tau(u) - tau(v) path. To guarantee that a G is H-linked, you need a minimum degree larger than vertical bar G vertical bar/2. This situation changes, if you know that G has a certain connectivity k. Depending on k, even a minimum degree independent of vertical bar G vertical bar may suffice. Let delta(k, H, N) be the minimum number such that every k-connected graph G with vertical bar G vertical bar = N and delta(G) >= delta(k, H, N) is H-linked. We study bounds for this quantity. In particular, we find bounds for all multigraphs H with at most three edges and some with four edges, which are optimal up to small additive or multiplicative constants. As a consequence, we also establish a few pure connectivity bounds for graph linkages.
机译：对于给定的多重图H，如果垂直条G垂直条> =垂直条H垂直条并且对于每个内射图tau：V（H）-> V（G），则图G是H链接的，我们可以找到内部不相交的路径在G中，使得uv中H中的每个边都对应于tau（u）-tau（v）路径。为了确保G是H链接的，您需要的最小角度大于垂直条G vertical bar / 2。如果您知道G具有特定的连通性k，这种情况就会改变。取决于k，即使是与竖线G，竖线无关的最小度也可以满足。设delta（k，H，N）为最小值，以使每个带有k的图G的竖线G竖线= N且delta（G）> = delta（k，H，N）被H链接。我们研究此数量的界限。特别是，我们找到了所有多图H的边界，这些边界最多具有三个边缘，有些具有四个边缘，这对于较小的加法或乘法常数都是最佳的。因此，我们还为图链接建立了一些纯连通性边界。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号