Counting and labeling grid related graphs

Christian Barrientos, Sarah Minion


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.


graceful, $\alpha$-labeling, fence, rigid grid

Full Text:




B. D. Acharya, Are all polyominoes arbitrarily graceful?, Proc. First Southeast Asian Graph Theory Colloquium, Ed. K. M. Koh and H. P. Yap, Springer-Verlag, N. Y. 1984, 205--211.

C. Barrientos and S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl., 74 (2015) 73--83.

C. Barrientos and S. Minion, Constructing graceful graphs with caterpillars, J. Algorithms and Computation, 48 (2016), 117--125.

C. Barrientos and S. Minion, On the graceful Cartesian product of alpha-trees, Theory Appl. Graphs, 4 (2017), no. 1, Art. 3, 12 pp.

C. Barrientos and S. Minion, Snakes: from graceful to harmonious, Bull. Inst. Combin. Appl., 79 (2017), 95--107.

G. Chartrand and L. Lesniak, Graphs & Digraphs, 2nd ed.,

Wadsworth & Brooks Cole (1986).

J.A. Gallian, emph{A dynamic survey of graph labelings}, Electron. J. Combin., (2018), #DS6.

D. Jungreis and M. Reid, Labeling grids, Ars Combin., 34 (1992) 167--182.

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967) 349--355.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats