随机图的广义3-连通度  

The Generalized 3-Connectivity of Random Graphs

作　　者：顾冉[1] 李学良[1] 史永堂[1] 

机构地区：[1]南开大学组合数学中心,天津300071

出　　处：《数学学报（中文版）》2014年第2期321-330,共10页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(11071130;11001140)

摘　　要：图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.The generalized connectivity of a graph G was introduced by Chartrand et al. Let S be a nonempty set of vertices of G, and k（S） denote the largest number of internally disjoint trees connecting S in G. Then for an integer r with 2 〈 r 〈 n, the generalized r-connectivity kr（G） of G is the minimum k（S） where S runs over all the r-subsets of the vertex set of G. Obviously, k2（G） = k（G）, is the vertex connectivity of G, and hence the generalized connectivity is a natural generalization of the vertex connectivity. In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer k ≥ 1,p=10gn＋（k＋1）loglogn-loglogn/nis a sharp threshold function for the property k3（G（n,p）） ≥ k, which could be seen as a counterpart of Bollobas and Thomason＇s result for vertex connectivity.

关 键 词：连通度 内部不交树 广义连通度 随机图 阈值函数 

分 类 号：O157.5[理学—数学]