## Abstract

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 Ω(n^{2-2/r}) edges. On the other hand, for any n ≥n_{0}(r), we explicitly construct H(r, n)-universal graphs G and Λ on n and 2n vertices, and with O(n^{2-Ω(1/r log r)}) and O(n^{2-1/r} log^{1/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} log^{1/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) |
---|---|

Pages (from-to) | 14-21 |

Number of pages | 8 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

DOIs | |

State | Published - 2000 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture