Triangle packing and covering in dense random graphs

Given a simple graph $$G=(V,E)$$ G = ( V , E ) , a subset of E is called a triangle cover if it intersects each triangle of G. Let $$\nu _t(G)$$ ν t ( G ) and $$\tau _t(G)$$ τ t ( G ) denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza (in: Finite and infinite sets, proceedings of Colloquia Mathematica Societatis, Janos Bolyai, p 888, 1981) conjectured in 1981 that $$\tau _t(G)/\nu _t(G)\le 2$$ τ t ( G ) / ν t ( G ) ≤ 2 holds for every graph G. In this paper, we consider Tuza’s Conjecture on dense random graphs. Under $$\mathcal {G}(n,p)$$ G ( n , p ) model with a constant p, we prove that the ratio of $$\tau _t(G)$$ τ t ( G ) and $$\nu _t(G)$$ ν t ( G ) has the upper bound close to 1.5 with high probability. Furthermore, the ratio 1.5 is nearly the best result when $$p\ge 0.791$$ p ≥ 0.791 . In some sense, on dense random graphs, these conclusions verify Tuza’s Conjecture.