2010/05/04 by Shasha Li, Xueliang Li, Li, Shasha +1
Computer Science · Mathematics · #05C05 #05C40 #68Q25 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C05 #msc:05C40 #msc:68Q25 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1005.0488
10 pages
arxiv created 2010/05/04 · arxiv updated 2010/05/05
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 κ(S) denote the maximum number ℓ of edge-disjoint trees T1,T2,...,T_ℓ in G such that V(Ti)∩ V(Tj)=S for every pair i,j of distinct integers with 1≤ i,j≤ ℓ. A collection \T1,T2,...,T_ℓ\ 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 κk(G), of G is defined by κk(G)=min\κ(S)\, where the minimum is taken over all k-subsets S of V(G). Thus κ2(G)=κ(G), where κ(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of the generalized connectivity. At first, we obtain that for two fixed positive integers k1 and k2, given a graph G and a k1-subset S of V(G), the problem of deciding whether G contains k2 internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k1 is a fixed integer of at least 4, but k2 is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k2 is a fixed integer of at least 2, but k1 is not a fixed integer, we show that the problem also becomes NP-complete. Finally we give some open problems.