Integer programming formulations and probabilistic bounds for some domination parameters

Mhelmar Labendia; Clifford Pornia

doi:10.56947/amcs.v30.618

Authors

Mhelmar Labendia Department of Mathematics and Statistics, Center for Mathematical and Theoretical Physical Sciences- PRISM, Mindanao State University-Iligan Institute of Technology, Philippines
Clifford Pornia Philippine Science High School - Soccsksargen Region Campus, Philippines

DOI:

https://doi.org/10.56947/amcs.v30.618

Keywords:

hop domination, 2-step domination, restrained domination, IP formulation, probabilistic bounds

Abstract

In this paper, we further study the concepts of hop domination and 2-step domination and introduce the concepts of restrained hop domination, total restrained hop domination, 2-step restrained domination, and total 2-step restrained domination in graphs. We then construct integer programming (IP) formulations and present probabilistic upper bounds for these domination parameters. IP is a powerful optimization technique widely applied in computer science to develop efficient algorithms.