Sharp bounds for the generalized connectivity kappa3(G)
Sharp bounds for the generalized connectivity kappa3(G)
复制标题
DOI：
10.1016/j.disc.2010.04.011
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Shasha Li;Xueliang Li;Wenli Zhou
中科院分区：
文献类型：
--
作者：
Shasha Li;Xueliang Li;Wenli Zhou
设G是一个n阶非平凡连通图，k是一个2≤k≤n的整数.对于G的k个顶点的集合S，设κ（S）表示G中满足V（Ti）<$V（Tj）=S的边不交树T1，T2，.，T <$的最大个数. G中具有此性质的树的集合{T1，T2，.，T}称为连接S的树的内部不交集。Chartrand等人将连通度的概念推广如下：G的k-连通度，记为κ k（G），定义为κk（G）=min{κ（S）}，其中最小值取V（G）的所有k-子集S。因此κ2（G）=κ（G），其中κ（G）是G的连通度。对于一般k，κk（G）的研究是非常困难的.因此，本文主要研究κ3（G）。研究了图的连通度与3-连通度之间的关系。首先给出了一般图G的κ3（G）的精确上、下界，并构造了两类分别达到上、下界的图.证明了若G是连通平面图，则κ（G）−1≤κ3（G）≤κ（G），并给出了几类达到这一界的图.最后给出了确定一般图G的κ3（G）的一个算法。该算法对于连通度固定的图是多项式时间的，这意味着对于最小度或连通度较小的图，确定κ3（G）的问题可以在多项式时间内得到解决，特别是对于平面图G，确定κ 3（G）是否等于κ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 κ(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 general k, the investigation of κk(G) is very difficult. We therefore focus on the investigation on κ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 κ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 κ(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) 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 κ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) for a planar graph G can be solved in polynomial time.