...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete mathematics >Removable edges in a k-connected graph and a construction method for k-connected graphs
【24h】

Removable edges in a k-connected graph and a construction method for k-connected graphs

机译：k连通图的可移动边和k连通图的构造方法

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

摘要

An edge e of a k-connected graph G is said to be a removable edge if G circle minus e is still k-connected, where G circle minus e denotes the graph obtained from G by deleting e to get G - e and, for any end vertex of e with degree k - 1 in G - e, say x, deleting x and then adding edges between any pair of non-adjacent vertices in NG-e(x)- Xu and Guo [Liqiong Xu, Xiaofeng Guo, Removable edges in a 5-connected graph and a construction method of 5-connected graphs, Discrete Math. 308 (2008) 1726-1731] proved that a 5-connected graph G has no removable edge if and only if G congruent to K-6, using this result, they gave a construction method for 5-connected graphs. A k-connected graph G is said to be a quasi (k + 1)-connected if G has no nontrivial k-vertex cut. Jiang and Su [Hongxing Jiang, Jianji Su, Minimum degree of minimally quasi (k + 1)-connected graphs, J. Math. Study 35 (2002) 187-193] conjectured that for k >= 4 the minimum degree of a minimally quasi k-connected graph is equal to k - 1. In the present paper, we prove this conjecture and prove for k >= 3 that a k-connected graph G has no removable edge if and only if G is isomorphic to either Kk+1 or (when k is even) the graph obtained from Kk+2 by removing a 1-factor. Based on this result, a construction method for k-connected graphs is given.
机译：如果G圆减去e仍与k相连，则k连通图G的边e被称为可移动边，其中G圆减去e表示通过删除e以获得G-e而从G获得的图。在G-e中度数为k-1的e的任意端点，例如x，删除x，然后在NG-e（x）-Xu和Guo中的任意一对非相邻顶点之间添加边[徐立琼，郭小峰，五连通图的可移动边缘和五连通图的构造方法，离散数学。 308（2008）1726-1731]证明了当且仅当G与K-6一致时，一个5连通图G才没有可移动边缘，使用该结果，他们给出了一种5连通图的构造方法。如果G没有非平凡的k顶点切割，则k连通图G称为准（k +1）连通。姜和苏[姜洪兴，苏建吉，最小拟（k + 1）连通图的最小程度，J。数学。研究35（2002）187-193]推测，对于k> = 4，最小拟k连通图的最小程度等于k-1。在本文中，我们证明了这种猜想，并证明k> = 3表示当且仅当G与Kk + 1或（当k为偶数时）同构同形（通过去除1因子）从Kk + 2获得时，k连通图G没有可移动边缘。基于此结果，给出了k个连通图的构造方法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号