A Turán-type generalization of Tuza’s triangle edge cover problem

Abstract

We investigate the smallest number λk(G) of edges that can be removed from a non-empty graph G so that the resulting graph contains no kclique. Turán’s theorem tells us that λk(Kn) is the number of edges missing from the Turán graph T (n, k − 1). The investigation of λ3(G) was initiated by Tuza. Let G(k) be the union of k-cliques of G. Let m, t, and κ be the number of edges of G(k), the number of k-cliques of G, and ( k 2 ) , respectively. We prove that λk(G) ≤ 2m+κt 3κ , and that equality holds if and only if the k-cliques of G are pairwise edge-disjoint. We also prove that λk(G) ≤ m ( 1− (κ−1 κ )( κt ) 1 κ−1 ) , and this bound is also attained by unions of pairwise edge-disjoint k-cliques