Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 21-26 |
Number of pages | 6 |
Journal | North-Holland Mathematics Studies |
Volume | 60 |
Issue number | C |
DOIs | |
State | Published - Jan 1 1982 |
ASJC Scopus subject areas
- General Mathematics