连通图的可收缩边和可去边

发布时间：2018-06-28 23:12

  本文选题：最长圈 + 生成树　； 参考：《广西师范学院》2017年硕士论文

【摘要】：图的连通性是图论的重要组成部分,因此研究连通图的构造一直是图论研究的重要课题之一.连通图的可收缩和可去边的存在性对于研究连通图结构有着重要作用.本文以5-连通图和κ-连通图为对象讨论了连通图在最长圈,生成树,完美匹配上可收缩边的分布情况以及可去边的性质.本文主要针对以下三方面进行论述:首先,利用原子,断片的性质,证明了不包含特殊2-断片的5-连通图最长圈C上至少有6条可收缩边,进一步证明了若C中不存在包含5度点的3圈,C上至少有2条可收缩边;证明了不包含特殊2-断片的5-连通图生成树H上至少有6条可收缩边,得到E(H)(?)En(G)的一类5-连通图Hn;给出了不包含特殊2-断片若完美匹配边不在3圈内的5-连通图完美匹配M上至少有8条可收缩边,进一步证明了若g(G) 4, M上至少有8条可收缩边.其次,研究了 κ-连通图可收缩边的分布,证明了若{x}(?)T点割且E(x)(?)En(G),则存在一点y,使d(y) =κ, y ∈∩ N(x).还给出了 κ-连通图最长圈,生成树和完美匹配上可收缩边更一般的下界.最后,研究了 κ-连通图可去边的性质,得到在满足最小度条件下κ-连通图生成树H上至少存在两条可去边.G的边点割原子阶至少为κκ - 3的κ-连通图,G[A]和G[S]上的边都是可去边.
[Abstract]:The connectivity of graphs is an important part of graph theory, so the study of the construction of connected graphs has always been one of the important topics in graph theory. The existence of contractible and detachable edges of connected graphs is very important for studying the structure of connected graphs. In this paper, we take 5-connected graphs and 魏 -connected graphs as objects to discuss the distribution of contractable edges on longest cycles, spanning trees, perfectly matched graphs and the properties of detachable edges of connected graphs. In this paper, the following three aspects are discussed: firstly, by using the properties of atoms and fragments, it is proved that there are at least six contractible edges on the longest cycle C of a 5-connected graph without special 2-fragment. It is further proved that there are at least two contractible edges in C and at least 6 retractable edges on the spanning tree H of 5-connected graph without special 2-segment. We obtain a class of 5-connected graphs of E (H) (?) E n (G), and give that there are at least eight contractible edges on the perfect matching M of 5-connected graphs without special 2-segment if the perfect matching edges are not in three cycles. It is further proved that if g (G) 4, there are at least eight contractible edges on M. Secondly, we study the distribution of retractable edges of 魏 -connected graphs, and prove that if {x} (?) T points are cut and E (x) (?) E n (G), then there exists a little ysuch that d (y) = 魏, y 鈭，

本文编号：2079766