The Domination Continuum
by
Miranda L. Roden
University of Alabama in Huntsville
Coauthors: Peter J. Slater (University of Alabama in Huntsville)

Motivated by problems involving placing detection devices in a graph G that models a facility or a computer processing network, and in which detection devices are subject to failure, we discuss the liar's domination number g_LR(G). For g_{x(2, 3)}(G) as defined next, we have g_LR(G)=g_{x(2, 3)}(G).

For each sequence c₁, c₂, c₃, c₄, ... with c_i ≤ c_i+1, we define a domination parameter g_{x(c1, c2, c3, ...)}(G). The requirement is for each vertex subset of size i to be dominated at least c_i times. We thus have an (uncountably) infinite lattice set of domination parameters. We focus on the 2-dimensional sublattice of parameters g_{x(c1, c2)}(G), with particular attention paid to trees, and examine the relationships among these parameters.

Date received: April 17, 2008