• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Extremal functions for graph linkages and rooted minors.
【24h】

Extremal functions for graph linkages and rooted minors.

机译：图链接和生根未成年人的极值功能。

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

摘要

A graph G is k-linked if for any 2k distinct vertices s1,..., sk,t1,...,tk there exist k vertex disjoint paths P1,..., Pk such that the endpoints of Pi are si and ti. Determining the existence of graph linkages is a classic problem in graph theory with numerous applications. In this thesis, we examine sufficient conditions that guarantee a graph to be k-linked and give the following theorems. (A) Every 2k-connected graph on n vertices with 5kn edges is k-linked. (B) Every 6-connected graph on n vertices with 5n - 14 edges is 3-linked. The proof method for Theorem (A) can also be used to give an elementary proof of the weaker bound that 8kn edges suffice. Theorem (A) improves upon the previously best known bound due to Bollobas and Thomason stating that 11kn edges suffice. The edge bound in Theorem (B) is optimal in that there exist 6-connected graphs on n vertices with 5n - 15 edges that are not 3-linked.; The methods used prove Theorems (A) and (B) extend to a more general structure than graph linkages called rooted minors. We generalize the proof methods for Theorems (A) and (B) to find edge bounds for general rooted minors, as well as finding the optimal edge bound for a specific family of bipartite rooted minors.; We conclude with two graph theoretical applications of graph linkages. The first is to the problem of determining when a small number of vertices can be used to cover all the odd cycles in a graph. The second is a simpler proof of a result of Bohme, Maharry and Mohar on complete minors in huge graphs of bounded tree-width.
机译：如果对于任何2k个不同的顶点s1，...，sk，t1，...，tk存在k个顶点不相交的路径P1，...，Pk，使得Pi的端点为si和，则图G是k链接的。 ti。确定图链接的存在是图论中具有许多应用的经典问题。在本文中，我们研究了保证图被k链接的充分条件，并给出了以下定理。 （A）在具有5kn边的n个顶点上的每个2k连通图都是k链接的。 （B）在具有5n-14条边的n个顶点上的每个6个连通图是3连通的。定理（A）的证明方法也可以用于给出8kn边缘足以满足的较弱边界的基本证明。定理（A）在Bollobas和Thomason指出11kn边缘就足够了的基础上改进了先前最广为人知的界线。定理（B）中的边边界是最佳的，因为在n个顶点上存在6个连通图，其中5n-15个未3链接的边。所用方法证明了定理（A）和（B）扩展到比称为根次要图的图链接更通用的结构。我们归纳了定理（A）和（B）的证明方法，以找到一般生根未成年人的边缘边界，以及找到特定的两部分生根未成年人家庭的最佳边缘边界。我们以图链接的两个图理论应用为结尾。第一个问题是确定何时可以使用少量顶点来覆盖图中的所有奇数循环。第二个更简单的证明是Bohme，Maharry和Mohar在完整的未成年人中以有界树宽为单位的巨大图中的结果。

著录项

  • 作者

    Wollan, Paul.;

  • 作者单位

    Georgia Institute of Technology.;

  • 授予单位 Georgia Institute of Technology.;
  • 学科 Mathematics.
  • 学位 Ph.D.
  • 年度 2005
  • 页码 145 p.
  • 总页数 145
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 数学;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号