20.500.12556/RUL-161300 Covering the edges of a graph with triangles In 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. edge-disjoint triangles edge clique covering Nordhaus-Gaddum inequality true false true Angleški jezik Ni določen Članek v reviji 2024-09-09 12:53:14 2024-09-09 12:53:16 2025-08-08 13:41:38 0000-00-00 00:00:00 2025 0 0 8 str. iss. 1, art. 114226 Vol. 348 Jan. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0012-365X 10.1016/j.disc.2024.114226 206292739 1-s2.0-S0012365X24003571-main.pdf 1-s2.0-S0012365X24003571-main.pdf 1 F0D05868F841D1EADBEC0CED74F5359E 56009e65abf3c367044398e25eedd3eab18ddcec66105fc5a0440d32f7ea77ee f375260f-6e99-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190202 https://www.sciencedirect.com/science/article/pii/S0012365X24003571 1 aedb6d33-6e99-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190201 Fakulteta za matematiko in fiziko 0 0 0