INTEGER PROGRAMMING APPROACHES TO TWO DOMINATION RELATED PROBLEMS IN GRAPH THEORY

Date

2025-7-04

Author

Arı, Çınar

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

11503
views

0
downloads

Cite This

In this thesis, two domination variants; namely, paired-domination and defensive domination, are studied using integer programming techniques. The first variant involves finding a dominating set (called a paired-dominating set) in a given simple graph which induces a subgraph that has a perfect matching. Assuming weights on the nodes and the edges, we study the problem of finding a paired-dominating set of minimum weight. For this problem, after proposing an initial integer programming formulation, we strengthen it and show that the linear programming relaxation of the latter characterizes the convex hull of the incidence vectors of paired-dominating sets in trees even though the constraint matrix is not always totally unimodular. Moreover, we initiate the study of the paired-dominating set polytope by proposing several sets of valid inequalities. The performance of the strengthened formulation and the impact of valid inequalities are analyzed via a computational study. The second variant looks for a dominating set (called a k-defensive dominating set) in a given simple graph which can defend against all attacks to any k nodes of the graph for a given positive integer k. A node in our dominating set can defend against at most one attacker in its closed neighborhood. Assuming weights on the nodes, we study the problem of finding a k-defensive dominating set of minimum weight. For this problem, we propose an integer programming formulation with exponentially many constraints, strengthen it via some valid inequalities and implement the strengthened formulation using a row generation procedure.

Subject Keywords

Integer programming, Domination, Paired-domination, Defensive domination, Valid Inequalities

URI

https://hdl.handle.net/11511/115172

Collections

Graduate School of Natural and Applied Sciences, Thesis