Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Covering the edges of a graph with triangles
Authors:ID Bujtás, Csilla (Author)
ID Davoodi, Akbar (Author)
ID Ding, Laihao (Author)
ID Győri, Ervin (Author)
ID Tuza, Zsolt (Author)
ID Yang, Donglei (Author)
Files:.pdf PDF - Presentation file, download (283,48 KB)
MD5: 96EE4727625D7B0BB38E7D45FC982644
 
URL URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0012365X24003571
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract: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.
Keywords:edge-disjoint triangles, edge clique covering, Nordhaus-Gaddum inequality
Publication status:Published
Publication version:Version of Record
Publication date:01.01.2025
Year of publishing:2025
Number of pages:8 str.
Numbering:Vol. 348, iss. 1, article no. 114226
PID:20.500.12556/DiRROS-20511 New window
UDC:519.17
ISSN on article:0012-365X
DOI:10.1016/j.disc.2024.114226 New window
COBISS.SI-ID:206292739 New window
Note:
Publication date in DiRROS:03.10.2024
Views:353
Downloads:187
Metadata:XML DC-XML DC-RDF
:
BUJTÁS, Csilla, DAVOODI, Akbar, DING, Laihao, GYŐRI, Ervin, TUZA, Zsolt and YANG, Donglei, 2025, Covering the edges of a graph with triangles. Discrete mathematics [online]. 2025. Vol. 348, no. 1,  114226. [Accessed 21 April 2025]. DOI 10.1016/j.disc.2024.114226. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=20511
Copy citation
  
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete mathematics
Shortened title:Discrete math.
Publisher:Elsevier
ISSN:0012-365X
COBISS.SI-ID:1118479 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0355
Name:Prirejanja, transverzale in hipergrafi
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov
Funder:Other - Other funder or multiple funders
Funding programme:National Natural Science Foundation of China
Project number:11901226
Funder:Other - Other funder or multiple funders
Funding programme:NKFIH
Project number:132696
Funder:Other - Other funder or multiple funders
Funding programme:NKFIH
Project number:SNN 129364
Funder:Other - Other funder or multiple funders
Funding programme:NKFIH
Project number:FK 132060
Funder:Other - Other funder or multiple funders
Funding programme:China Postdoctoral Science Foundation
Project number:2021T140413
Funder:Other - Other funder or multiple funders
Funding programme:Natural Science Foundation of China
Project number:12101365
Funder:Other - Other funder or multiple funders
Funding programme:Natural Science Foundation of Shandong Province
Project number:ZR2021QA029

Licences

License:CC BY-NC 4.0, Creative Commons Attribution-NonCommercial 4.0 International
Link:http://creativecommons.org/licenses/by-nc/4.0/
Description:A creative commons license that bans commercial use, but the users don’t have to license their derivative works on the same terms.

Back