文献类型：期刊文献

英文题名：On the difference of two generalized connectivities of a graph

作者：Sun, Yuefang[1];Li, Xueliang[2]

机构：[1]Shaoxing Univ, Dept Math, Shaoxing 312000, Zhejiang, Peoples R China;[2]Nankai Univ, Ctr Combinator, Tianjin, Peoples R China

年份：2017

卷号：33

期号：1

起止页码：283

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：SCI-EXPANDED(收录号：WOS:000392817300020)、、EI(收录号：20153801276809)、Scopus(收录号：2-s2.0-84941333065)、WOS

基金：Yuefang Sun was supported by NSFC No. 11401389 and Xueliang Li was supported by NSFC No. 11371205, and PCSIRT. We thank the anonymous referees for their careful reading of our work and helpful suggestions.

语种：英文

外文关键词：k-connectivity; Generalized k-connectivity; Tree connectivity

外文摘要：The concept of k-connectivity. k(k)' (G) of a graph G, introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. Another generalized connectivity of a graph G, named the generalized k-connectivity. k(k)(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of these two parameters by showing that for a connected graph G of order n, if. k(k)' (G) not equal n -k + 1 where k >= 3, then 0 <= k(k)'(G) -k(k)(G) <= n-k-1; otherwise, -[k/2] + 1 <= k(k)'(G)-k(k)(G) <= n-k. Moreover, all of these bounds are sharp. Some specific study is focused for the case k = 3. As results, we characterize the graphs with. k(3)'(G) =k(3)(G) = t for t is an element of {1, n-3, n-2}, and give a necessary condition for k(3)'(G) =k(3)(G) by showing that for a connected graph G of order n and size m, if k(3)'(G) =k(3)(G) = t where 1 <= t <= n-3, then m <= ((n-2)(2)) + 2t. Moreover, the unique extremal graph is given for the equality to hold.