Covering the edges of a graph with triangles

Abstrakt

In a graph G, let ρ△(G) denote the minimum size of a set of edges and triangles that cover all edges of G, and let α1(G) be the maximum size of an edge set that contains at most one edge from each triangle. Motivated by a question of Erdős, Gallai, and Tuza, we study the relationship between ρ△(G) and α1(G) and establish a sharp upper bound on ρ△(G). We also prove Nordhaus-Gaddum-type inequalities for the considered invariants.