Constructing edge extremal triangle-free graphs with bounded maximum degree and matching number using integer programming
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2023.
Abstract
The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1], and a structure for an extremal graph has been provided in [2]. Then, finding the edge count of an extremal graph with forbidden subgraphs emerged as a new problem. Ahanjideh, Ekim, and Yıldız [3] worked on triangle-free graphs and solved the cases for d ≥ m and for d < m with either d ≤ 6 or Z(d) ≤ m < 2d, where Z(d) is approximately 5d/4. They also provided a structure for an extremal graph for the rest. Using the structure provided, we develop an integer programming formulation for constructing an extremal graph. The formulation is highly symmetric. We use our implementation of orbital branching and objective perturbation to reduce symmetry. We also propose an exact iterative algorithm that partitions the feasible region based on upper bounds and works iteratively on a limited space. Using a combination of the orbital branching and iterative approaches, we expand the solution into d < 11 instead of d < 7 for m > d and show that conjectures proposed in [3] hold, thus strengthening them.