首页 | 本学科首页   官方微博 | 高级检索  
     检索      

5连通图中的可去边
引用本文:徐丽琼,郭晓峰.5连通图中的可去边[J].数学研究与评论,2011,31(4):617-626.
作者姓名:徐丽琼  郭晓峰
作者单位:集美大学理学院, 福建 厦门 361023;厦门大学数学学院, 福建 厦门 361005
基金项目:国家自然科学基金(Grant No.10831001),
摘    要:An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G 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, delete x, and then add edges between any pair of non-adjacent vertices in NG-e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated 1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least (3│G│ + 2)/2 removable edges.

关 键 词:5-connected  graph  removable  edge  edge-vertex-atom.
收稿时间:7/8/2009 12:00:00 AM
修稿时间:2010/1/18 0:00:00

Removable Edges in a 5-Connected Graph
Li Qiong XU and Xiao Feng GUO.Removable Edges in a 5-Connected Graph[J].Journal of Mathematical Research and Exposition,2011,31(4):617-626.
Authors:Li Qiong XU and Xiao Feng GUO
Institution:1. School of Sciences, Jimei University, Fujian, 361023, P.R.China
2. School of Mathematics Sciences, Xiamen University,Fujian,361005,P.R.China
Abstract:An edge $e$ of a $k$-connected graph $G$ is said to be a removable edge if $G\ominus e$ is still $k$-connected, where $G\ominus 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$, delete $x$, and then add edges between any pair of non-adjacent vertices in $N_{G-e}(x)$. The existence of removable edges of $k$-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated 1,\,11,\,14,\,15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5-connected graph. Based on the properties, we proved that for a 5-connected graph $G$ of order at least 10, if the edge-vertex-atom of $G$ contains at least three vertices, then $G$ has at least $(3|G|+2)/2$ removable edges.
Keywords:5-connected graph  removable edge  edge-vertex-atom  
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《数学研究与评论》浏览原始摘要信息
点击此处可从《数学研究与评论》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号