| Summary: | <p>In this work we explore some graphs associated with the grid <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>. A fence is any subgraph of the grid obtained by deleting any feasible number of edges from some or all the copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>. We present here a closed formula for the number of non-isomorphic fences obtained from <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>, for every <span class="math"><em>m</em>, <em>n</em> ≥ 2</span>. A rigid grid is a supergraph of the grid, where for every square a pair of opposite vertices are connected; we show that the number of fences built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> is the same that the number of rigid grids built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em> + 1</sub></span>. We also introduce a substitution scheme that allows us to substitute any interior edge of any <span class="math"><em>P</em><sub><em>m</em></sub></span> in an <span class="math"><em>α</em></span>-labeled copy of <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> to obtain a new graph with an <span class="math"><em>α</em></span>-labeling. This process can be iterated multiple times on the <span class="math"><em>n</em></span> copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>; in this way we prove the existence of an <span class="math"><em>α</em></span>-labeling for any graph obtained via these substitutions; these graphs form a quite robust family of <span class="math"><em>α</em></span>-graphs where the grid is one of its members. We also show two subfamilies of disconnected graphs that can be obtained using this scheme, proving in that way that they are also <span class="math"><em>α</em></span>-graphs.</p>
|
|---|