Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Covering the edges of a graph with triangles
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
)
PDF - Presentation file,
Download
(270,06 KB)
MD5: F0D05868F841D1EADBEC0CED74F5359E
URL - Source URL, Visit
https://www.sciencedirect.com/science/article/pii/S0012365X24003571
Image galllery
Abstract
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.
Language:
English
Keywords:
edge-disjoint triangles
,
edge clique covering
,
Nordhaus-Gaddum inequality
Work type:
Article
Typology:
1.01 - Original Scientific Article
Organization:
FMF - Faculty of Mathematics and Physics
Publication status:
Published
Publication version:
Version of Record
Year:
2025
Number of pages:
8 str.
Numbering:
Vol. 348, iss. 1, art. 114226
PID:
20.500.12556/RUL-161300-57bb6709-7cc1-4a07-023f-830cf48f3157
UDC:
519.17
ISSN on article:
0012-365X
DOI:
10.1016/j.disc.2024.114226
COBISS.SI-ID:
206292739
Publication date in RUL:
09.09.2024
Views:
38
Downloads:
20
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Discrete mathematics
Shortened title:
Discrete math.
Publisher:
Elsevier
ISSN:
0012-365X
COBISS.SI-ID:
1118479
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.
Projects
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
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back