本文選題：3-連通圖 + 可收縮邊��； 參考：《廣西師范學院》2017年碩士論文

【摘要】：圖構造的研究是圖論中的重要基礎理論研究,對圖論的發(fā)展有著重大的影響和推動作用.圖的可收縮邊是研究連通圖的結構的強有力工具,在歸納證明連通圖的性質中有著重要的作用.本文主要對k-連通圖的可收縮子圖進行研究.主要結果如下:若3-連通圖G存在一棵生成樹H使得H中的邊都是不可收縮邊,則稱G是fox.本文對fox的局部結構進行了研究,證明了3-連通圖fox中的3度點恰好關聯(lián)一條不可收縮邊.證明了極小fox中的不可收縮邊的數(shù)目恰好是|V(G)|-1.即極小fox中存在唯一一棵生成樹H使得H中的邊都是不可收縮邊.對極小臨界fox中的3度點的數(shù)目進行了估計,證明了至少有V(G)(10)1/2個3度點.證明了fox圖G的特殊子圖H周圍存在子圖H,使G/H'還是fox.這為給出fox的歸納構造提供了可能.若3-連通圖G存在一棵生成樹H使得H中至多有一條可收縮邊,則稱G是擬fox.對擬fox的局部結構進行了研究,證明了其局部存在六種可能的結構.在此基礎上對3-連通圖深度優(yōu)先搜索(DFS)生成樹上的可收縮邊數(shù)目進行了估計,證明了若3-連通圖G的DFS生成樹H的根不是3度點,則H中至少有兩條可收縮邊.有例子表明我們的條件是不能夠減弱的.最后對極大臨界k-連通圖G上的可收縮邊進行刻畫,證明了G中一定存在可收縮邊e,使G/e仍是臨界k-連通圖.
[Abstract]:The study of graph construction is an important basic theory research in graph theory, which has a great influence on the development of graph theory. The contractible edge of a graph is a powerful tool for studying the structure of a connected graph and plays an important role in the induction and proof of the properties of a connected graph. In this paper, we study the retractable subgraphs of k-connected graphs. The main results are as follows: if there exists a spanning tree H in 3-connected graph G such that the edges in H are all non-contractive edges, then G is called fox. In this paper, the local structure of fox is studied, and it is proved that the 3-degree point in 3-connected graph fox is exactly associated with a non-contractive edge. It is proved that the number of non-retractable edges in the minimal fox is exactly the number of the VG)-1. That is, there exists only one spanning tree H in minimal fox such that the edges in H are non-contractive. The number of 3 degree points in minimal critical fox is estimated and it is proved that there are at least 3 V(G)(10)1/2 points. It is proved that there exists a subgraph H around the special subgraph H of fox graph G so that G / H'is fox. This makes it possible to give the inductive structure of fox. If a 3-connected graph G has a spanning tree H such that there is at most one contractible edge in H then G is called quasi fox. The local structure of quasi fox is studied and six possible structures are proved. On this basis, the number of contractible edges on the spanning tree of 3-connected graph depth first search is estimated. It is proved that if the root of the DFS spanning tree H of 3-connected graph G is not a 3-degree point, then there are at least two contractible edges in H. There are examples that show that our conditions cannot be weakened. Finally, the retractable edges on maximal critical k- connected graph G are characterized, and it is proved that there must be retractable edges in G, so that G / e is still a critical k- connected graph.
【學位授予單位】：廣西師范學院
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【參考文獻】

相關期刊論文 前6條

1 王珊珊;齊恩鳳;;k-連通圖中最長圈上可收縮邊的數(shù)目[J];山東大學學報(理學版);2015年10期

2 崔燕飛;王世英;;某些7-連通圖最長圈上的可收縮邊[J];太原師范學院學報(自然科學版);2013年03期

3 鐘玲平;崔慶;;臨界k連通圖中的點度數(shù)[J];應用數(shù)學學報;2012年05期

4 盧建立;張志芳;;6-連通圖最長圈上的可收縮邊[J];科技導報;2010年21期

5 楊朝霞;;某些5-連通圖中最長圈上的可收縮邊[J];山東大學學報(理學版);2008年06期

6 吳吉昌,李學良;4-連通圖中圈上的可去邊和可收縮邊[J];廈門大學學報(自然科學版);2003年05期

，

本文編號：1984551