  The secure domination problem, a variation of the domination problem with
some important real-world applications, is considered. Very few algorithmic
attempts to solve this problem have been presented in literature, and the most
successful to date is a binary programming formulation which is solved using
CPLEX. A new binary programming formulation is proposed here which requires
fewer constraints and fewer binary variables than the existing formulation. It
is implemented in CPLEX, and tested on certain families of graphs that have
previously been considered in the context of secure domination. It is shown
that the runtime required for the new formulation to solve the instances is
significantly less than that of the existing formulation. An extension of our
formulation that solves the related, but further constrained, secure connected
domination problem is also given; to the best of the authors' knowledge, this
is the first such formulation in literature.

Combinatorics;Discrete Mathematics;Optimization and Control