本文選題：最長圈 + 生成樹　； 參考：《廣西師范學(xué)院》2017年碩士論文

【摘要】：圖的連通性是圖論的重要組成部分,因此研究連通圖的構(gòu)造一直是圖論研究的重要課題之一.連通圖的可收縮和可去邊的存在性對于研究連通圖結(jié)構(gòu)有著重要作用.本文以5-連通圖和κ-連通圖為對象討論了連通圖在最長圈,生成樹,完美匹配上可收縮邊的分布情況以及可去邊的性質(zhì).本文主要針對以下三方面進行論述:首先,利用原子,斷片的性質(zhì),證明了不包含特殊2-斷片的5-連通圖最長圈C上至少有6條可收縮邊,進一步證明了若C中不存在包含5度點的3圈,C上至少有2條可收縮邊;證明了不包含特殊2-斷片的5-連通圖生成樹H上至少有6條可收縮邊,得到E(H)(?)En(G)的一類5-連通圖Hn;給出了不包含特殊2-斷片若完美匹配邊不在3圈內(nèi)的5-連通圖完美匹配M上至少有8條可收縮邊,進一步證明了若g(G) 4, M上至少有8條可收縮邊.其次,研究了 κ-連通圖可收縮邊的分布,證明了若{x}(?)T點割且E(x)(?)En(G),則存在一點y,使d(y) =κ, y ∈∩ N(x).還給出了 κ-連通圖最長圈,生成樹和完美匹配上可收縮邊更一般的下界.最后,研究了 κ-連通圖可去邊的性質(zhì),得到在滿足最小度條件下κ-連通圖生成樹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