On Graphs Which Contain All Sparse Graphs

From MaRDI portal





Let \(s(n)\) denote the maximum number of edges in a graph \(G\) which contains as subgraphs all graphs with \(n\) edges. The authors prove that for sufficiently large \(n\) \(cn^2/\log^2n<s(n)<c'n^2\log\log n/\log n\) (here \(c\) and \(c'\) are constants). It is also proved that the minimum number of edges in a graph which contains all planal graphs with \(n\) edges is less than \(cn^{3/2}\). The proofs are prohabilistic (which might not be a surprise) and short (10\% of the paper is taken up by redoubtable list of authors). For the entire collection see [Zbl 0485.00006].




Cited in
(31)








This page was built for publication: On Graphs Which Contain All Sparse Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3958492)