Constructing extremal triangle-free graphs using integer programming
Discrete Optimization, cilt.50, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 50
- Basım Tarihi: 2023
- Doi Numarası: 10.1016/j.disopt.2023.100802
- Dergi Adı: Discrete Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
- Anahtar Kelimeler: Extremal graphs, Factor-critical, Integer programming, Orbital branching
- Boğaziçi Üniversitesi Adresli: Evet
Özet
The maximum number of edges in a graph with matching number m and maximum degree d has been determined in Chvátal and Hanson (1976) and Balachandran and Khare (2009), where some extremal graphs have also been provided. Then, a new question has emerged: how the maximum edge count is affected by forbidding some subgraphs occurring in these extremal graphs? In Ahanjideh et al. (2022), the problem is solved in triangle-free graphs for d≥m, and for d