Covering the edges of a graph with trianglesBujtás, Csilla (Avtor) Davoodi, Akbar (Avtor) Ding, Laihao (Avtor) Győri, Ervin (Avtor) Tuza, Zsolt (Avtor) Yang, Donglei (Avtor) edge-disjoint trianglesedge clique coveringNordhaus-Gaddum inequalityIn a graph $G$, let $\rho_\triangle(G)$ denote the minimum size of a set of edges and triangles that cover all edges of $G$, and let $\alpha_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 $\rho_\triangle(G)$ and $\alpha_1(G)$ and establish a sharp upper bound on $\rho_\triangle(G)$. We also prove Nordhaus-Gaddum-type inequalities for the considered invariants.20252024-10-03 11:29:42Neznano20511UDK: 519.17ISSN pri članku: 0012-365XDOI: 10.1016/j.disc.2024.114226COBISS_ID: 206292739sl