Random Graphs from Planar and Other Addable Classes
Random Graphs from Planar and Other Addable Classes
复制标题
来自平面和其他可添加类的随机图
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
D. Welsh
中科院分区：
文献类型：
--
作者：
C. McDiarmid;A. Steger;D. Welsh
本文研究随机图Rn的各种性质，随机图Rn是从n个标号顶点上的简单图类（mathcal{A}_n）中随机均匀抽取的，且满足一定的性质，如平面图或树宽不超过κ.特别是，我们表明，如果类（mathcal{A}）是“小”和“可添加的”，那么概率R n是连接的有界远离0和1。除了连通性，我们还研究子图的外观，因此也研究顶点度和自同构的数量。我们进一步看到，如果（mathcal{A}）是“光滑的”，那么我们可以做出更精确的陈述，例如关于连通性的陈述。
We study various properties of a random graph R n , drawn uniformly at random from the class ( mathcal{A}_n ) of all simple graphs on n labelled vertices that satisfy some given property, such as being planar or having tree-width at most κ. In particular, we show that if the class ( mathcal{A} ) is’ small’ and ‘addable’, then the probability that R n is connected is bounded away from 0 and from 1. As well as connectivity we study the appearances of subgraphs, and thus also vertex degrees and the numbers of automorphisms. We see further that if ( mathcal{A} ) is’ smooth’ then we can make much more precise statements for example concerning connectivity.