<![CDATA[In this work we explore some graphs associated with the grid Pm × Pn. A fence is any subgraph of the grid obtained by deleting any feasible number of edges from some or all the copies of Pm. We present here a closed formula for the number of non-isomorphic fences obtained from Pm × Pn, for every m, n ≥ 2. 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 Pm × Pn is the same that the number of rigid grids built on Pm × Pn + 1. We also introduce a substitution scheme that allows us to substitute any interior edge of any Pm in an α-labeled copy of Pm × Pn to obtain a new graph with an α-labeling. This process can be iterated multiple times on the n copies of Pm; in this way we prove the existence of an α-labeling for any graph obtained via these substitutions; these graphs form a quite robust family of α-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 α-graphs.]]>
Copyrights © 2019
