5连通图中的可去边
Removable Edges in a 5-Connected Graph

DOI：10.3770/j.issn:1000-341X.2011.04.005

 作者 单位 徐丽琼 集美大学理学院, 福建 厦门 361023 郭晓峰 厦门大学数学学院, 福建 厦门 361005

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