期刊
DISCRETE MATHEMATICS
卷 310, 期 15-16, 页码 2147-2163出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disc.2010.04.011
关键词
Connectivity; k-connectivity; Internally disjoint trees (paths); Path-boundle
类别
资金
- NSFC
- PCSIRT
- 973 program
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据