TY - JOUR

T1 - On graphs which contain all sparse graphs

AU - Babai, L.

AU - Chung, F. R K

AU - Erdös, P.

AU - Graham, R. L.

AU - Spencer, J. H.

PY - 1982/1/1

Y1 - 1982/1/1

N2 - This chapter presents a study on graphs which contain all sparse graphs. Let ℋn denote the class of all graphs with n edges and denote by s(n) the minimum number of edges a graph G can have, which contains all H ∊ ℋn as subgraphs. The chapter discusses the problem of determining the minimum number of edges, denoted by s'(n) a graph can have, which contains every planar graph on n edges as a subgraph. The chapter discusses a lower bound for s(n) and while discussing an upper bound for s(n), it is proved (by the probability method) that there exists a graph with cn2 log log n/log n edges that contains all graphs with at most n edges. The chapter presents a theorem to give an upper bound of n3/2 for the universal graphs that contain all planar graphs on n edges.

AB - This chapter presents a study on graphs which contain all sparse graphs. Let ℋn denote the class of all graphs with n edges and denote by s(n) the minimum number of edges a graph G can have, which contains all H ∊ ℋn as subgraphs. The chapter discusses the problem of determining the minimum number of edges, denoted by s'(n) a graph can have, which contains every planar graph on n edges as a subgraph. The chapter discusses a lower bound for s(n) and while discussing an upper bound for s(n), it is proved (by the probability method) that there exists a graph with cn2 log log n/log n edges that contains all graphs with at most n edges. The chapter presents a theorem to give an upper bound of n3/2 for the universal graphs that contain all planar graphs on n edges.

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

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

U2 - 10.1016/S0304-0208(08)73486-8

DO - 10.1016/S0304-0208(08)73486-8

M3 - Article

AN - SCOPUS:77956952158

SN - 0304-0208

VL - 60

SP - 21

EP - 26

JO - North-Holland Mathematics Studies

JF - North-Holland Mathematics Studies

IS - C

ER -