Covering the edges of a graph with triangles

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00604135" target="_blank" >RIV/67985807:_____/25:00604135 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.disc.2024.114226" target="_blank" >https://doi.org/10.1016/j.disc.2024.114226</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.disc.2024.114226" target="_blank" >10.1016/j.disc.2024.114226</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Covering the edges of a graph with triangles
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Covering the edges of a graph with triangles
Popis výsledku anglicky
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.

Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2025
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)