Akademik Veri Yönetim Sistemi
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, cilt.12, sa.5, 2020 (ESCI)
Let G = (V, E) be a graph. A subset S subset of V of vertices is a dominating set if every vertex in V - S is adjacent to at least one vertex of S. The domination number is the minimum cardinality of a dominating set. Let u, v is an element of V. Then, u strongly dominates v and v weakly dominates u if (i) uv is an element of E and (ii) deg u >= deg v. A subset D of V is a strong (weak) dominating set of G if every vertex in V - D is strongly (weakly) dominated by at least one vertex in D. The strong (weak) domination number of G is the minimum cardinality of a strong (weak) dominating set. A set D subset of V is an independent (or stable) set if no two vertices of D are adjacent. The independent domination number of C (independent strong domination number, independent weak domination number, respectively) is the minimum size of an independent dominating set (independent strong dominating set, independent weak dominating set, respectively) of G. In this paper, mathematical models are developed for the problems of independent domination and independent strong (weak) domination of a graph. Then test problems are solved by the GAMS software, the optima and execution times are implemented. To the best of our knowledge, this is the first mathematical programming formulations for the problems, and computational results show that the proposed models are capable of finding optimal solutions within a reasonable amount of time.