Triangle-Covered Graphs: Algorithms, Complexity, and Structure

The widely studied edge modification problems ask how to minimally alter a graph to satisfy certain structural properties. In this paper, we introduce and study a new edge modification problem centered around transforming a given graph into a triangle-covered graph (one in which every vertex belongs to at least one triangle). We first present tight lower bounds on the number of edges in any connected triangle-covered graph of order n, and then we characterize all connected graphs that attain this minimum edge count. For a graph G, we define the notion of a Δ-completion set as a set of non-edges of G whose addition to G results in a triangle-covered graph. We prove that the decision problem of finding a Δ-completion set of size at most t0 is NP-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains NP-complete even when the input is restricted to connected bipartite graphs. We then study the problem from an algorithmic perspective, providing tight bounds on the minimum Δ-completion set size for several graph classes, including trees, chordal graphs, and cactus graphs. Furthermore, we show that the triangle-covered problem admits an (n +1) -approximation algorithm for general graphs. For trees and chordal graphs, we design algorithms that compute minimum Δ-completion sets. Finally, we show that the threshold for a random graph G (n, p) to be triangle-covered occurs at n^-2/3.