Sparse universal graphs for bounded‐degree graphs
Sparse universal graphs for bounded‐degree graphs
复制标题
有界度图的稀疏通用图
DOI：
10.1002/rsa.20143
复制
发表时间：
2007
影响因子：
1
通讯作者：
Michael R. Capalbo
中科院分区：
文献类型：
--
作者：
N. Alon;Michael R. Capalbo
设h︁是一个图族。如果图T包含每个H∈H︁的副本作为子图，则图T是H︁‐全域的。设h h︁（k,n）表示有n个顶点且最大度数不超过k的图族。对于所有正整数k和n，我们构造了一个h h︁（k,n）‐全称图T，它有$O_k(n^{2-{2 \ / k}} \log ^{4 \ / k} n)$条边和恰好n个顶点。边的数量几乎尽可能少，因为Ω（n2‐2/k）是任何这样的图中边数量的下界。T的构造是显式的，而通用性的证明是概率性的，并且是基于一个新的图分解结果和展开式上随机游走的性质。©2006 Wiley期刊公司随机结构。Alg。, 2007年
Let ℋ︁ be a family of graphs. A graph T is ℋ︁‐universal if it contains a copy of each H ∈ℋ︁ as a subgraph. Let ℋ︁(k,n) denote the family of graphs on n vertices with maximum degree at most k. For all positive integers k and n, we construct an ℋ︁(k,n)‐universal graph T with $O_k(n^{2-{2 \over k}} \log ^{4 \over k} n)$ edges and exactly n vertices. The number of edges is almost as small as possible, as Ω(n2‐2/k) is a lower bound for the number of edges in any such graph. The construction of T is explicit, whereas the proof of universality is probabilistic and is based on a novel graph decomposition result and on the properties of random walks on expanders. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007