Enumeration of 2-factored dominating sets in fixed-width grid graphs

Abstract

<p>A <em><span class="math inline">\(2\)</span>-factored dominating set</em> (<span class="math inline">\(2\)</span>fd-set) of a graph <span class="math inline">\(G=(V,E)\)</span> is a dominating set <span class="math inline">\(F\subseteq V\)</span> such that the induced subgraph <span class="math inline">\(G[F]\)</span> is <span class="math inline">\(2\)</span>-regular, and hence is a disjoint union of cycles. In this study, <span class="math inline">\(2\)</span>-factored dominating sets on fixed-width grid graphs of dimensions <span class="math inline">\(m \times n\)</span>, where <span class="math inline">\(m \in \{2,3,4\}\)</span>, are enumerated. We establish theorems describing the generating functions with respect to the number of <span class="math inline">\(2\)</span>-factored dominating sets in these grid graphs. The number of <span class="math inline">\(2\)</span>-factored dominating sets grows exponentially with <span class="math inline">\(n\)</span>, with growth constant determined by the dominant singularity of the generating function.</p>