K-连通图中的可收缩边

发布时间：2018-06-06 02:14

本文选题：3-连通图 + 可收缩边　；参考：《广西师范学院》2017年硕士论文

【摘要】：图构造的研究是图论中的重要基础理论研究,对图论的发展有着重大的影响和推动作用.图的可收缩边是研究连通图的结构的强有力工具,在归纳证明连通图的性质中有着重要的作用.本文主要对k-连通图的可收缩子图进行研究.主要结果如下:若3-连通图G存在一棵生成树H使得H中的边都是不可收缩边,则称G是fox.本文对fox的局部结构进行了研究,证明了3-连通图fox中的3度点恰好关联一条不可收缩边.证明了极小fox中的不可收缩边的数目恰好是|V(G)|-1.即极小fox中存在唯一一棵生成树H使得H中的边都是不可收缩边.对极小临界fox中的3度点的数目进行了估计,证明了至少有V(G)(10)1/2个3度点.证明了fox图G的特殊子图H周围存在子图H,使G/H'还是fox.这为给出fox的归纳构造提供了可能.若3-连通图G存在一棵生成树H使得H中至多有一条可收缩边,则称G是拟fox.对拟fox的局部结构进行了研究,证明了其局部存在六种可能的结构.在此基础上对3-连通图深度优先搜索(DFS)生成树上的可收缩边数目进行了估计,证明了若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

【参考文献】