【作者】 李玮；

【导师】 李学良；

【作者基本信息】 南开大学 ， 应用数学， 2012， 博士

【摘要】 连通度是图论的基本概念之一，它常被用来衡量一个通讯网络的性能。一个通讯网络可以自然地表示成图的形式，而连通度就是为使这个图不连通所需移除的元素（顶点或边）的最小数目，因此连通度越高也就意味着这个通讯网络的性能越好。连通度被众多的数学家进行研究。近年来，数学家们又提出了一些新的连通度概念，如彩虹连通度，广义连通度等，从不同的侧重点研究图的连通性质。这篇论文的主要结果就是关于广义连通度的一些进展。令G为一个具有n个顶点的非平凡连通图， k为一个整数，满足2≤k≤n。对G的一个k-元子集S，用κ(S)表示G中边不交树T1,T2,...,T的数目，这些树要满足V(Ti)∩V (Tj)=S，对每对不同的整数i, j，其中1≤i, j≤(注意到这些树在G\S中是顶点不交的)。G中满足这一性质的一族树{T1,T2,...,T}称为连接S的内部不交树集。图G的k-连通度，记为κk(G)，定义为κk(G)=min{κ(S)}，其中最小是取遍V (G)的所有k-元子集S。因此，κ2(G)=κ(G)，而κn(G)是G的边不交生成树的数目.本文的第一章主要介绍一些记号和定义，以及相关的结果等。在第二章中，我们设计了一种方法——列表方法，利用这种方法我们可以方便而快捷的找到任意完全二部图的所有边不交生成树。我们还计算了完全二部图的所有广义k-连通度并得到下面的结果：令a，b为满足a≤b的任意两个正整数，如果k> b a+2，且a b+k是奇数，那么在第三章中，我们将列表方法进一步用于完全三部图，可以找到任意完全三部图的所有边不交生成树。应用数学分析和近似算法等中的一些技巧，我们计算出了等部完全三部图的所有广义k-连通度。对满足b≥2且3≤k≤3b的任意两个整数b，k，等部完全三部图K3在第四章中，我们用图的分解以及匹配的一些方法，找到了完全多部图G的所有m(G)n(G)1棵边不交生成树，其中m(G)表示G的边数，n(G)表示G的顶点数。我们还根据完全二部图和等部完全三部图的广义k-连通度的结果，提出了关于完全多部图的广义k-连通度的一些猜想。更多还原

【Abstract】 Connectivity is one of the basic concepts of graph theory, it is often used to mea-sure the performance of a communication network. A communication network can berepresented as a graph naturally, while the connectivity of the graph is the minimumnumber of elements (vertices or edges) which need to be removed to disconnect thegraph. Therefore the higher the connectivity of the graph means the better the perfor-mance of the communication network. Connectivity is studied by many mathemati-cians. In recent years, mathematicians have also proposed some new concepts aboutconnectivity, such as rainbow connection, generalized connectivity and so on. Theystudy the connectivity property of graphs from different emphases. The main results ofthis thesis are about some development of generalized connectivity.Let G be a nontrivial connected graph of order n, and k an integer with2≤k≤n.For a set S of k vertices of G, let κ(S) denote the number of edge-disjoint treesT1,T2,...,T in G such that V(Ti)∩V (Tj)=S for every pair i, j of distinct integers with1≤i, j≤(Note that the trees are vertex-disjoint in G\S). A collection {T1,T2,...,T}of trees in G with this property is called an internally disjoint set of trees connectingS. The k-connectivity, denoted by κk(G), of G is then defined as κk(G)=min{κ(S)},where the minimum is taken over all k-subsets S of V (G). Thus, κ2(G)=κ(G) andκn(G) is the number of edge-disjoint spanning trees of G.In Chapter1, we introduce some notation, definitions and related results.In Chapter2, we design a method—list method. Using this method we can find alledge-disjoint spanning trees of any complete bipartite graph conveniently and rapidly.Then we compute k-connectivity of all complete bipartite graphs for2≤k≤n andget the following results: Let a, b be any two positive integers such that a≤b. Ifk> b a+2and a b+k is odd, then In Chapter3, we apply list method to complete3-partite graphs. With this methodwe can find all edge-disjoint spanning trees of any complete3-partite graph. Then weuse some techniques in mathematical analysis and approximation algorithms to com-pute k-connectivity of all complete equipartition3-partite graphs for3≤k≤n. Forany two integers b, k such that b≥2and3≤k≤3b, the k-connectivity of completeequipartition3-partite graph K3In Chapter4, we use some techniques in decomposition of graphs and matchingto find allm(G)n(G)1edge-disjoint spanning trees of complete equipartition multipartitegraph G, where m(G) denotes the number of edges of G and n(G) denotes the numberof vertices of G. We also propose some conjectures about k-connectivity of completeequipartition multipartite graphs according to the results of k-connectivity of completebipartite graphs and complete equipartition3-partite graphs.更多还原