The Number of Snakes in a Box

Year 2018, , 145 - 156, 25.12.2018

Christian Barrientos , Sarah Minion

https://doi.org/10.33401/fujma.453324

Abstract

Within the class of polyominoes we work on the enumeration of two subfamilies of the family of snake polyominoes: stairs and snakes of height 2. We consider them from a graph theoretical perspective. In the process of enumeration of these graphs, we use classical ideas, as symmetries, and a new approach that connects these snakes with the partitions of integers.

Keywords

Partition, Polyomino, Snake

References

• [1] D. Battaglino, A. Frosini, V. Guerrini, Binary pictures with excluded patters, Discrete Geometry for Computer Imagery, 18th IAPR International Conference, (2014), 25–38.
• [2] S. W. Golomb, (2nd ed.), Polyominoes: Ouzzles, Patterns, Problems, and Packings, Princeton University Press, Princeton, MA, 1996.
• [3] A. Goupil, M.-E. Pellerin, J. de Wouters d’Oplinter, Partially directed snake polyominoes, Discrete Appl. Math., 236 (2018), 223–234.
• [4] E. Pegg Jr., https://oeis.org/A002013, 2009.
• [5] C. Barrientos, Graceful labelings of cyclic snakes, Ars Combin., 60 (2001), 85–96.
• [6] C. Barrientos, S. Minion, Snakes: from graceful to harmonious, Bull. Inst. Combin. Appl., 79 (2017), 95–107.
• [7] N. J. A. Sloane, R. K. Guy, https://oeis.org/A005418, 2012.
• [8] 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.
• [9] C. Barrientos, S. Minion, On the number of a-labeled graphs, Discuss. Math. Graph Theory, 38 (2018), 177–188.
• [10] J. A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin., (2017), #DS6.
• [11] E. Deutsch, https://oeis.org/A102547, 2010.
• [12] N. J. A. Sloane, https://oeis.org/A226916, 2013.
• [13] G. McGarvey,, https://oeis.org/A102543, 2005.
• [14] N. J .A. Sloane, https://oeis.org/A078012, 2002.