Counting and labeling grid related graphs
Christian Barrientos, Sarah Minion · Electronic Journal of Graph Theory and Applications · 2019
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.