...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Connectivity of k-extendable graphs with large k
【24h】

Connectivity of k-extendable graphs with large k

机译：具有大k的k可扩展图的连通性

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

摘要

Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0≤k≤n-1), G is k-extendable if any matching of size k in G is contained in a perfect matching of G. It is proved that if G is a k-extendable graph on 2n vertices with k≥n/2, then either G is bipartite or the connectivity of G is at least 2k. As a corollary, we show that if G is a maximal k-extendable graph on 2n vertices with n+2≤2k+1, then G is K_(n,n) if k+1≤δ≤n and G is K_(2n) if 2k+1≤δ≤2n-1. Moreover, if G is a minimal k-extendable graph on 2n vertices with n+1≤2k+1 and k+1≤δ≤n then the minimum degree of G is k+1. We also discuss the relationship between the k-extendable graphs and the Hamiltonian graphs.
机译：令G是2n个顶点上具有完美匹配的简单连接图。对于给定的正整数k（0≤k≤n-1），如果在G的完美匹配中包含G中大小k的任何匹配，则G是k可扩展的。证明了如果G是k可扩展的图在k≥n/ 2的2n个顶点上，则G是二分的，或者G的连通度至少为2k。作为推论，我们证明如果G是n +2≤2k+ 1的2n个顶点上的最大k可扩展图，那么如果k +1≤δ≤n且G为K_（，则G为K_（n，n）。 2n）如果2k +1≤δ≤2n-1。此外，如果G是在n +1≤2k+ 1和k +1≤δ≤n的2n个顶点上的最小k可扩展图，则G的最小度为k + 1。我们还讨论了k可扩展图和哈密顿图之间的关系。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号