Sparse universal graphs

Noga Alon, Vera Asodi

Research output: Contribution to journalArticle

16 Scopus citations

Abstract

For every n, we describe an explicit construction of a graph on n vertices with at most O(n2-ε) edges, for ε=0.133..., that contains every graph on n vertices with maximum degree 3 as a subgraph. It is easy to see that each such graph must have at least Ω(n4/3) edges. We also show that the minimum number of edges of a graph that contains every graph with n edges as a subgraph is Θ(n2/(log2 n)). This improves a result of Babai, Chung, Erdös, Graham and Spencer (Ann. Discrete Math. 12 (1982) 21-26).

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalJournal of Computational and Applied Mathematics
Volume142
Issue number1
DOIs
StatePublished - May 1 2002

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

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

  • Cite this