Sharp bounds for the generalized connectivity κ3(G)κ3(G)

Let GG be a nontrivial connected graph of order nn and let kk be an integer with 2≤k≤n2≤k≤n. For a set SS of kk vertices of GG, let κ(S)κ(S) denote the maximum number ℓℓ of edge-disjoint trees T1,T2,…,TℓT1,T2,…,Tℓ in GG such that V(Ti)∩V(Tj)=SV(Ti)∩V(Tj)=S for every pair i,ji,j of distinct integers with 1≤i,j≤ℓ1≤i,j≤ℓ. A collection {T1,T2,…,Tℓ}{T1,T2,…,Tℓ} of trees in GG with this property is called an internally disjoint set of trees connecting SS. Chartrand et al. generalized the concept of connectivity as follows: The kk-connectivity  , denoted by κk(G)κk(G), of GG is defined by κk(G)=min{κ(S)}κk(G)=min{κ(S)}, where the minimum is taken over all kk-subsets SS of V(G)V(G). Thus κ2(G)=κ(G)κ2(G)=κ(G), where κ(G)κ(G) is the connectivity of GG. For general kk, the investigation of κk(G)κk(G) is very difficult. We therefore focus on the investigation on κ3(G)κ3(G) in this paper. We study the relation between the connectivity and the 33-connectivity of a graph. First we give sharp upper and lower bounds of κ3(G)κ3(G) for general graphs GG, and construct two kinds of graphs which attain the upper and lower bound, respectively. We then show that if GG is a connected planar graph, then κ(G)−1≤κ3(G)≤κ(G)κ(G)−1≤κ3(G)≤κ(G), and give some classes of graphs which attain the bounds. In the end we give an algorithm to determine κ3(G)κ3(G) for general graphs GG. This algorithm runs in a polynomial time for graphs with a fixed value of connectivity, which implies that the problem of determining κ3(G)κ3(G) for graphs with a small minimum degree or connectivity can be solved in polynomial time, in particular, the problem whether κ(G)=κ3(G)κ(G)=κ3(G) for a planar graph GG can be solved in polynomial time.