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 -