On The Generalized Connectivity Of Complete Multipartite Graphs

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.