Covering and independence in triangle structures (Q1916100)

A graph is triangular if each edge is contained in at least one triangle. In the paper under review, several results concerning the following two invariants are proved. For \(i= 1,2\) we have: (1) \(\alpha_i(G)\) is the smallest cardinality of an edge set containing at least \(i\) edges of each triangle, and (2) \(\tau_i(G)\) is the largest cardinality of an edge set containing at most \(i\) edges of each triangle. For example, every triangular graph \(G\) with \(n\) vertices satisfies \(\alpha_i(G)\leq\lfloor(n-1)^2/4\rfloor\), and every connected graph with \(n\) vertices satisfies \(\alpha_1(G)\geq(n-1)/2\). There is a positive constant \(c\) such that \(\alpha_1(G)+\tau_1(G)\geq ce^{2/3}\) holds for every graph \(G\) with \(e\) edges and \(\alpha_1(G)+\tau_1(G)\leq e-ce^{1/3}\) for every triangular graph with \(e\) edges.