1,2-efficiency in grid graphs

<p>Let <span class="math inline">\(G = (V, E)\)</span> be a graph with vertex set <span class="math inline">\(V\)</span> and edge set <span class="math inline">\(E\)</span>. A vertex set <span class="math inline">\(S \subset V\)</span> is a <span><em>perfect dominating set</em></span> if every vertex in <span class="math inline">\(V - S\)</span> is adjacent to exactly one vertex in <span class="math inline">\(S\)</span>. A perfect dominating set <span class="math inline">\(S\)</span> is furthermore: (i) an <span><em>efficient dominating set</em></span> or a <span><em><span class="math inline">\(1\)</span>-efficient dominating set</em></span> if no two vertices in <span class="math inline">\(S\)</span> are adjacent, (ii) a <span><em>total efficient dominating set</em></span> or a <span><em><span class="math inline">\(2\)</span>-efficient dominating set</em></span> if every vertex in <span class="math inline">\(S\)</span> is adjacent to exactly one other vertex in <span class="math inline">\(S\)</span>, and (iii) a <span><em><span class="math inline">\(1,2\)</span>-efficient dominating set</em></span> if every vertex in <span class="math inline">\(S\)</span> either adjacent to no vertices in <span class="math inline">\(S\)</span> or to exactly one other vertex in <span class="math inline">\(S\)</span>. In this paper we introduce the concept of <span><em><span class="math inline">\(1,2\)</span>-efficiency</em></span> in graphs and apply it to the existence of <span class="math inline">\(1,2\)</span>-efficient sets in <span><em>grid graphs</em></span> <span class="math inline">\(G_{m,n}\)</span>, that is, graphs resembling chessboards having a rectangular array of <span class="math inline">\(m \times n\)</span> vertices arranged into <span class="math inline">\(m\)</span> rows of <span class="math inline">\(n\)</span> vertices, or <span class="math inline">\(n\)</span> columns of <span class="math inline">\(m\)</span> vertices. It is well known that almost no grid graphs are <span class="math inline">\(1\)</span>-efficient, and relatively few grid graphs are <span class="math inline">\(2\)</span>-efficient. However, in this paper, we show that all but a relatively small percentage of grid graphs are <span class="math inline">\(1,2\)</span>-efficient.</p>