Some Topies On Generalized Connectivity Of Graphs

The connectivity κ（G） of a graph G, which is one of the basic concepts of graphtheory, is defined as the minimum cardinality of a set Q of vertices of G such that G Qis disconnected or trivial. A well-known theorem of Whitney provides an equivalentdefinition of connectivity. For each2-subset S={u, v} of V （G）, letκ（S） denote themaximum number of internally disjoint uv-paths in G. Then κ（G）=min{κ（S）}, wherethe minimum is taken over all2-subsets S of V （G）.Chartrand et al. generalized the concept of connectivity. Let G be a nontrivialconnected graph of order n and let k be an integer with2≤k≤n. For a set S of k verticesof G, let κ（S） denote the maximum number of edge-disjoint trees T₁,T₂,...,T in Gsuch that V （T_i）∩V （T_j）=S for every pair i, j of distinct integers with1≤i, j≤. Thek-connectivity, denoted by κ_k（G）, of G is then defined by κ_k（G）=min{κ（S）}, wherethe minimum is taken over all k-subsets S of V （G）. Thus κ2（G）=κ（G）. Moreover,κ_n（G） is exactly the maximum number of edge-disjoint spanning trees of G, and thena well-known theorem of Nash-Williams and Tutte can be restated as follows: for anygraph G, κ_n（G）≥k if and only if for every partition P of its vertex set it has at leastk（|P|1） cross-edges, edges whose ends lie in different partition sets. In addition tobeing a natural combinatorial measure, generalized connectivity can also be motivatedby its interesting interpretation in practice.This thesis includes four chapters. In Chapter1, we introduce the definition andthe background of generalized connectivity, and give the basic notations and terminol-ogy related to this thesis. We also present an overview of results on the generalizedconnectivity, including the main results of this thesis.For a general graph G and a general positive integer k, to get the exact value ofκ_k（G） is very difficult. Therefore, in Chapter2, we first focus on the investigation ofκ₃and mainly study the relationship between the2-connectivity and the3-connectivityof a graph. We get sharp upper and lower bounds of κ₃（G） for general graphs G, andconstruct two kinds of graphs which attain the upper and lower bounds, respectively. Next we show that if G is a connected planar graph, then κ（G）1≤κ₃（G）≤κ（G）,and give some classes of graphs which attain the bounds. Finally, we discuss the rela-tionship between κ_kand κ_k-1. We obtain that for a cubic graph G, κ_k（G）≤κ_k-1（G）for3≤k≤n, but for a general graph G, the claim is not true. Moreover, we prove thatif3≤k≤6, thenκ_k（G）≤κ（G） for any graph G. But for any integer k≥7, we canalways give a graph with κ_k> κ.In Chapter3, we contribute to the complexity of determining the generalized con-nectivity of a graph. Firstly, we give an algorithm to determine whether κ₃（G）≥k fora general graph G. This algorithm runs in polynomial time if k is a fixed positive inte-ger, which implies that the problem of determining κ₃（G） for a graph G with a smallminimum degree or connectivity can be solved in polynomial time, in particular, theproblem whether κ（G）=κ₃（G） for a planar graph G can be solved in polynomial time.Then, by generalizing the algorithm of determining κ₃（G）, we obtain that if k1and k2are two fixed positive integers, given a graph G and a k1-subset S of V （G）, the problemof deciding whether G contains k2internally disjoint trees connecting S can be solvedby a polynomial-time algorithm. But when k1is a fixed integer of at least4, and k2is not a fixed integer, we show that the problem turns out to be NP-complete. On theother hand, when k2is a fixed integer of at least2, but k1is not a fixed integer, we showthat the problem also becomes NP-complete. In the end of this chapter, we give twoconjectures on the generalized connectivity.In Chapter4, we are interested in some extremal problems on the size of a graphwith κ₃≥2. We first consider the minimal size guaranteeingκ₃≥2and obtain thatgiven any positive integer n≥4, there exists a smallest integer f （n）=n23n22+3suchthat every graph G of order n and size e（G）≥f （n） hasκ₃（G）≥2. Next, we turn tothe minimal size of a graph with κ₃=2. For a graph G of order n and size e（G） withκ₃（G）=2, we prove that e（G）≥65n, and the lower bound is sharp for all n≥4butn=9,10, whereas for n=9,10we give examples to show that65n+1is the bestpossible lower bound. Finally, we study the size of a graph G which is minimal forκ₃=2. We give the sharp lower bound of e（G）. But for the sharp upper bound g（n）of e（G）, we only obtain that2n4≤g（n）≤3n10. To determine the exact value ofg（n） is still an open problem.