For any positive integers r and n, let H(r, n) denote the family of graphs on n vertices with maximum degree r, and let H(r, n, n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r, n)-universal graph must have Ω(n2-2/r) edges. On the other hand, for any n ≥n0(r), we explicitly construct H(r, n)-universal graphs G and Λ on n and 2n vertices, and with O(n2-Ω(1/r log r)) and O(n2-1/r log1/r n)edges, respectively, such that we can efficiently find a copy of any H∈H(r, n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G = G(n, n, p), with p = cn-1/2r log1/2r n is fault-tolerant; for a large enough constant c, even after deleting any α-fraction of the edges of G, the resulting graph is still H(r, a(α)n, a(α)n)-universal for some a:[0, 1)→(0, 1].
|Original language||English (US)|
|Number of pages||8|
|Journal||Annual Symposium on Foundations of Computer Science - Proceedings|
|State||Published - Jan 1 2000|
All Science Journal Classification (ASJC) codes
- Hardware and Architecture