摘要
图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E(G),若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论:①如果P:x=x1x2…xn=y是6-连通图G的一条最长(x,y)-路,xixi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;②设P:x=x1x2…xn=y是6-连通图G的一条最长(x,y)-路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d(xi)≥7或者若d(xi)=6则[V(P)]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果:任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。
Contractible edges and removable edges in connected graphs are a powerful tool to study the structures of connected graphs and to prove some properties of connected graphs by induction. Let G be a 6-connected graph, an edge of G is called a 6-contractible edge if its contraction remains a 6-connected graph. In this paper, we adopt the method of a tree structure theory and obtain the following results： （1） Let P：x=x1x2...xn=y is the longest road of G, xixi＋1 is an uncontractible edge, and S={xi, xi＋1, u1, u2, u3, u4} is the corresponding 6-vertex cut, then there is at least one vertex of P in every fragment of G-S. （2） Let P：.x=x1x2…xn=y is the longest road of G, and any fragment＇s order is bigger than 2. If any vertex in P satisfies the condition （a） d（xi）≥ 7 or （b） if d（xi）=6, there is no 3-circle which contains the vertex, there is at least one contractible edge in P. Based on the above results, we consider an arbitrary fragment whose order is greater than 2, and the contractible edge＇s distribution in the longest cycle of 6-connected graphs and obtains the following result： if arbitrary fragment＇s order is greater than 2, then there are at least two contractible edges in the longest circle of 6-connected graphs.
出处
《科技导报》
CAS
CSCD
北大核心
2010年第21期75-77,共3页
Science & Technology Review
基金
河南省杰出青年计划项目(084100510013)
关键词
连通度
可收缩边
断片
端片
connected graphs
contractible edges
cut-fragment
end-fragment
