5连通图中的可去边

Removable Edges in a 5-Connected Graph

中文关键词:  5连通图  可去边  边点割原子.

英文关键词:5-connected graph  removable edge  edge-vertex-atom.

中文摘要:

      设$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.