Sparse universal graphs
type: Item
instance of: scholarly article
title: Sparse universal graphs
zbMATH Open document ID: 0997.05047
DOI: 10.1016/S0377-0427(01)00455-1
author: Noga Alon
author: Vera Asodi
published in: Journal of Computational and Applied Mathematics
publication date: 2002-08-22T00:00:00Z
review text: Improving a recent result of Alon et al., Alon and Asodi give an explicit construction of a graph of order \(n\) having \(O(n^{2-\varepsilon})\) edges, for \(\varepsilon=0.133\dots \), that is universal for the graphs of order \(n\) and maximum degree three, i.e. it contains all such graphs as subgraphs. As a second main result the authors prove that the minimum number of edges in a graph that is universal for the graphs having at most \(n\) edges and no isolated vertices is \(\Theta ( \frac{n^2}{\log^2 n})\) which proves that a corresponding lower bound due to Babai et al. is essentially best-possible. The proofs strongly rely on probabilistic methods.
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1787592
zbMATH Keywords: universal graph
MaRDI profile type: Publication
cites work: Q4004078
cites work: On Graphs Which Contain All Sparse Graphs
cites work: Universal Graphs for Bounded-Degree Trees and Planar Graphs
cites work: Q4252284
cites work: Small universal graphs
cites work: Q5620621
description: scientific article; zbMATH DE number 1787592