A note on sparse random graphs and cover graphs

MaRDI QIDQ1972677zbMATH OpenFDO

Authors Tom Bohman, Miklós Ruszinkó, Luboš Thoma, Alan Frieze

Publication date 16 April 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/120356, http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r19.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cover graphposetrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Review text

Summary: It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph \(G_{n,p}\) with \(p\leq \kappa\log n/n\) for any constant \(\kappa<2/3\). On the other hand, this is not true for somewhat higher densities: If \(p\geq \lambda (\log n)^3 / (n\log\log n)\) with \(\lambda > 1/8\) then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.

Recommendations

• scientific article; zbMATH DE number 2079333
• Triangle packing and covering in dense random graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Dense graphs with a large triangle cover have a large triangle packing
• Covering the edges of a random graph by cliques

Cited in

(1)

• On Cover Graphs and Dependent Arcs in Acyclic Orientations

This page was built for publication: A note on sparse random graphs and cover graphs

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