On Tuza's Conjecture in Dense Graphs

Abstract

In 1982, Tuza conjectured that the size $\tau (G)$ of a minimum set of edges that intersects every triangle of a graph $G$ is at most twice the size $\nu (G)$ of a maximum set of edge-disjoint triangles of $G$. This conjecture was proved for several graph classes. In this paper, we present three results regarding Tuza's Conjecture for dense graphs. By using a probabilistic argument, Tuza proved its conjecture for graphs on $n$ vertices with minimum degree at least $\frac{7n}{8}$. We extend this technique to show that Tuza's conjecture is valid for split graphs with minimum degree at least $\frac{3n}{5}$; and that $\tau (G)<\frac{28}{15}\nu (G)$ for every tripartite graph with minimum degree more than $\frac{33n}{56}$. Finally, we show that $\tau (G)\le \frac{3}{2}\nu (G)$ when $G$ is a complete 4-partite graph. Moreover, this bound is tight.

12 pages, 1 figure