Sharp bounds for the generalized connectivity κ3(G)

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