Random Graph Coverings I: General Theory and Graph Connectivity
Random Graph Coverings I: General Theory and Graph Connectivity
复制标题
随机图覆盖 I：一般理论和图连通性
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
N. Linial
中科院分区：
文献类型：
--
作者：
Alon Amit;N. Linial
在这篇文章中，我们描述了一个简单的模型，它具有到固定有限基图的n重覆盖映射。粗略地说，给定一个基图G和一个整数n，我们将G的每个顶点替换为n个顶点的集合，并当对应的顶点在G中相邻时通过随机匹配连接这些集合，从而形成一个随机图。从局部同构的意义上讲，所得到的图覆盖了原始图。我们建议了该模型的可能应用，例如以一种比标准随机模型提供的更可控的方式构造具有极值性质的图，并将给定的图“随机化”。我们在这里证明的主要具体结果(定理1)是：如果是G中的最小顶点度，则几乎所有的n-覆盖都是连通的。在接下来的文章中，我们将讨论图的其他性质，如围长、扩展和色数。
In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number.