TY - JOUR

T1 - Sparse universal graphs

AU - Alon, Noga

AU - Asodi, Vera

N1 - Funding Information:
Research supported in part by a USA–Israel BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2002/5/1

Y1 - 2002/5/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0036566508&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036566508&partnerID=8YFLogxK

U2 - 10.1016/S0377-0427(01)00455-1

DO - 10.1016/S0377-0427(01)00455-1

M3 - Article

AN - SCOPUS:0036566508

SN - 0377-0427

VL - 142

SP - 1

EP - 11

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

IS - 1

ER -