Maximum size of a triangle-free graph with bounded maximum degree and matching number

Milad Ahanjideh (), Tınaz Ekim () and Mehmet Akif Yıldız ()
Additional contact information
Milad Ahanjideh: Boğaziçi University
Tınaz Ekim: Boğaziçi University
Mehmet Akif Yıldız: Universiteit van Amsterdam

Journal of Combinatorial Optimization, 2024, vol. 47, issue 4, No 4, 21 pages

Abstract: Abstract Determining the maximum number of edges under degree and matching number constraints have been solved for general graphs in Chvátal and Hanson (J Combin Theory Ser B 20:128–138, 1976) and Balachandran and Khare (Discrete Math 309:4176–4180, 2009). It follows from the structure of those extremal graphs that deciding whether this maximum number decreases or not when restricted to claw-free graphs, to $$C_4$$ C 4 -free graphs or to triangle-free graphs are separately interesting research questions. The first two cases being already settled in Dibek et al. (Discrete Math 340:927–934, 2017) and Blair et al. (Latin American symposium on theoretical informatics, 2020), in this paper we focus on triangle-free graphs. We show that unlike most cases for claw-free graphs and $$C_4$$ C 4 -free graphs, forbidding triangles from extremal graphs causes a strict decrease in the number of edges and adds to the hardness of the problem. We provide a formula giving the maximum number of edges in a triangle-free graph with degree at most d and matching number at most m for all cases where $$d\ge m$$ d ≥ m , and for the cases where $$d

Keywords: Extremal graphs; Triangle-free graphs; Erdős–Stone’s Theorem; Turan’s Theorem; Integer programming; 05C35; 05C55 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01123-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01123-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01123-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().