Counting and labeling grid related graphs

Abstract

In this work we explore some graphs associated with the grid P_m × P_n. A fence is any subgraph of the grid obtained by deleting any feasible number of edges from some or all the copies of P_m. We present here a closed formula for the number of non-isomorphic fences obtained from P_m × P_n, 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 P_m × P_n is the same that the number of rigid grids built on P_m × P_n + 1. We also introduce a substitution scheme that allows us to substitute any interior edge of any P_m in an α-labeled copy of P_m × P_n to obtain a new graph with an α-labeling. This process can be iterated multiple times on the n copies of P_m; 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.