徐丽琼,郭晓峰.5连通图中的可去边[J].数学研究及应用,2011,31(4):617~626
5连通图中的可去边
Removable Edges in a 5-Connected Graph
投稿时间:2009-07-08  最后修改时间:2010-01-18
DOI:10.3770/j.issn:1000-341X.2011.04.005
中文关键词:  5连通图  可去边  边点割原子.
英文关键词:5-connected graph  removable edge  edge-vertex-atom.
基金项目:国家自然科学基金(Grant No.10831001);福建省青年科技人才创新基金(Grant No.2007F3070).
作者单位
徐丽琼 集美大学理学院, 福建 厦门 361023 
郭晓峰 厦门大学数学学院, 福建 厦门 361005 
摘要点击次数: 1266
全文下载次数: 1672
中文摘要:
      设$e$是$k$连通图$G$的一条边, $G\ominus e$表示图$G$做以下运算所得的图: (1) 从$G$中去掉$e$得图$G-e$; (2) 如果$e$的某个端点在$G-e$中度数为$k-1$,则去掉此端点,再两两联结此端点在$G-e$中的$k-1$个邻点. (3)如果经过(2)中的运算后,有重边出现,则用单边代替它们,使得此图为简单图. 若$G\ominus e$仍为$k$连通图, 则称$e$为$G$的可去边. $k$连通图中可去边的存在性以及3连通图和4连通图的可去边已被研究. 本文主要讨论5连通图中可去边的一些性质和分布;得到5连通图中圈上, 生成树上可去边的分布.由此可得阶至少为10的5连通图, 如果$G$的边点割原子的阶至少3, 则$G$中至少有$(3|G| 2)/2$条可去边.
英文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器