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

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

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

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

摘要

An edge e of a k-connected graph G is said to be a removable edge if Ge is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465–473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187–193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245–256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217–228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74–87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434–438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K6. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K6 by a number of θ+-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either Kk+1 or the graph Hk/2+1 obtained from Kk+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to Kk+1.
机译：如果Ge仍然是k-连接的，则k-连接图G的边缘e被称为可去除边缘。如果G没有非平凡的k分隔符，则将k连通图G称为准（k + 1）连通。研究了3连通图和4连通图的可移动边的存在以及拟k连通图的一些性质[D.A. Holton，B. Jackson，A. Saito，N.C. Wormale，三连通图中的可移动边，J。Graph Theory 14（4）（1990）465-473; H. Jiang，J。Su，最小拟（k + 1）连通图的最小程度，J。Math。研究35（2002）187–193; T. Politof，A。Satyanarayana，准四连通图的次要内容，离散数学。 126（1994）245-256; T. Politof，A。Satyanarayana，准四连通图的结构，离散数学。 161（1996）217–228; J. Su，三联图中可移动边的数量，J。Combin。理论系列B 75（1）（1999）74-87; J.阴，四联图的可移动边缘和构造，J。Systems Sci。数学。科学19（4）（1999）434–438]。在本文中，我们首先研究了准连通性与可移动边缘之间的关系。基于该关系，研究了k个连通图（k5）中可移动边的存在。证明了当且仅当它与K6同构时，5连通图没有可移动边。对于一个k连通图G，使得G的任意边的末端顶点最多具有k-3个共同的相邻顶点，这也证明了G具有可移动的边。因此，建立了五连通图的递归构造方法，即，可以通过多个θ+运算从K6获得任何五连通图。我们推测，如果k为偶数，则通过去除k / 2 + 1个不相交的边而没有可移动边缘的k个连通图G与Kk + 1或从Kk + 2获得的图Hk / 2 + 1同构，并且，如果k为奇数，则G与Kk + 1同构。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号