期刊文献+

关于随机相交图中Hamilton圈的门限函数的注记

A Note on Sharp Thresholds for Hamiltonicity in Random Intersection Graphs
下载PDF
导出
摘要 随机相交图G(n,m,p)的定义如下:记V为一n顶点集.M为一m个元素的集合.对每个顶点v∈V,赋予一随机子集Fv■M,其中从M中独立以概率p选取每个元素构成Fv,顶点u和v之间有边相连当且仅当Fu∩Fv≠Φ.当m=na,a≠1时.C.Efthymiou和P.G.Spirakis得到了G(n,m,p)中Hamilton圈的门限函数.对于a=1情形,本文利用二阶矩方法(Chebyshev不等式)得到了类似结果. The random intersection graph G (n,m,p) is deiined as tollows. Let V be a set of n nodes and M a set ot m elements. To each node v ∈ V , We assign a random subset Fv lohtain M , where Fv consists of elements in which each element is randomly and independently included with probability p from M. There is a edge between u and v if and only if Eu∩Fv≠Ф C. Efthymiou and P. G. Spirakis in [3] give sharp thresholds for the Hamilton cycle when re=n^a, where ct is different from 1. We get sharp threshold Pn= logn/n for Hamilton cycle when a = 1 using the second method. n
作者 刘沈荣
出处 《邵阳学院学报(自然科学版)》 2009年第2期11-12,共2页 Journal of Shaoyang University:Natural Science Edition
关键词 随机相交图 HAMILTON圈 门限函数 game coloring hamihonian random graph
  • 相关文献

参考文献4

  • 1M.Karonski,E.R.Scheinerman,K.Singer-Cohen.On random intersection graphs:the subgraph problem[].CombinatoricsProbability and Computing.1999
  • 2J.A.Fill,E.R.Scheinerman,K.Singer-Cohen.Random intersection graphs when m=ω(n):an equiva-lence theorem relating the evolution of G(n,m,p)andG(n,p)mod-els[].Random Structrues and Al-girithems.2000
  • 3C.Efthymiou,P.G.Spirakis.Sharp thresholds for Hamiltonicity in random intersection Graphs[]..
  • 4Bollobas B.Random graphs[]..2001

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部