The diamond‐free process
The diamond‐free process
复制标题
无金刚石工艺
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Michael E. Picollelli
中科院分区：
文献类型：
--
作者：
Michael E. Picollelli
设K4−表示菱形图，它是从完全图K4中去掉一条边而形成的。我们考虑以下随机图过程：从n个孤立顶点开始，随机均匀地添加边，只要没有这样的边创建K4−的副本。我们证明，当n→∞时，概率趋于1，所产生的图的最终大小是Θ（log <$n·n3/2）。我们的分析还表明，添加i条边后产生的图类似于均匀随机图，附加条件是不位于三角形上的边形成随机子图。© 2013威利期刊公司.随机结构算法，45，513-551，2014
Let K4− denote the diamond graph, formed by removing an edge from the complete graph K4. We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of K4− . We show that, with probability tending to 1 as n→∞ , the final size of the graph produced is Θ(logn·n3/2) . Our analysis also suggests that the graph produced after i edges are added resembles the uniform random graph, with the additional condition that the edges which do not lie on triangles form a random‐looking subgraph. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 513–551, 2014