Sparse universal graphs

Noga Alon; Vera Asodi

doi:10.1016/S0377-0427(01)00455-1

Sparse universal graphs

Noga Alon
, Vera Asodi

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

For every n, we describe an explicit construction of a graph on n vertices with at most O(n^2-ε) 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 Ω(n^4/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 Θ(n²/(log² n)). This improves a result of Babai, Chung, Erdös, Graham and Spencer (Ann. Discrete Math. 12 (1982) 21-26).

Original language	English (US)
Pages (from-to)	1-11
Number of pages	11
Journal	Journal of Computational and Applied Mathematics
Volume	142
Issue number	1
DOIs	https://doi.org/10.1016/S0377-0427(01)00455-1
State	Published - May 1 2002
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computational Mathematics
Applied Mathematics

Access to Document

10.1016/S0377-0427(01)00455-1

Cite this

@article{a7d37535c79f43faac95b3ae444966e5,

title = "Sparse universal graphs",

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{\"o}s, Graham and Spencer (Ann. Discrete Math. 12 (1982) 21-26).",

author = "Noga Alon and Vera Asodi",

note = "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. ",

year = "2002",

month = may,

day = "1",

doi = "10.1016/S0377-0427(01)00455-1",

language = "English (US)",

volume = "142",

pages = "1--11",

journal = "Journal of Computational and Applied Mathematics",

issn = "0377-0427",

publisher = "Elsevier B.V.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/0036566508

UR - https://www.scopus.com/pages/publications/0036566508#tab=citedBy

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 -

Sparse universal graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this