Packing and Covering Triangles in Dense Random Graphs

摘要

Given a simple graph G = (V,E), a subset of E is called a triangle cover if it intersects each triangle of G. Let ν_t(G) and τ_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 [25] conjectured in 1981 that τ_t(G)/ ν_t(G) ≤ 2 holds for every graph G. In this paper, we consider Tuza's Conjecture on dense random graphs. We prove that under G(n,p) model with p = Ω(1), for any 0 ＜ ∈ ＜ 1, τ_t(G) ≤ 1.5(1 + ∈) ν_t(G) holds with high probability, and under G(n,m) model with m = Ω(n~2), for any 0＜ ∈ ＜ 1, τ_t(G) ≤ 1.5(1 +∈) ν_t(G) holds with high probability. In some sense, on dense random graphs, these conclusions verify Tuza's Conjecture.