Sparse universal graphs for bounded-degree graphs

Noga Alon, Michael Capalbo

Research output: Contribution to journalArticle

37 Scopus citations

Abstract

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 Ok(n2-2/k log4/k n) edges and exactly n vertices. The number of edges is almost as small as possible, as Ω(n 2-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.

Original languageEnglish (US)
Pages (from-to)123-133
Number of pages11
JournalRandom Structures and Algorithms
Volume31
Issue number2
DOIs
StatePublished - Sep 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Sparse universal graphs for bounded-degree graphs'. Together they form a unique fingerprint.

  • Cite this