Some families of $\alpha$-labeled subgraphs of the integral grid

Document Type : Original paper

Authors

1 Department of Mathematics Valencia College Orlando, FL 32832 United States

2 Department of Mathematics Full Sail University Orlando, FL 32792 United States

Abstract

In this work we study the most restrictive variety of graceful labelings, that is, we study the existence of an $\alpha$-labeling for some families of graphs that can be embedded in the integral grid. Among the categories of graphs considered here we have a subfamily of 2-link fences, a subfamily of column-convex polyominoes, and a subfamily of irregular cyclic-snakes. We prove that under some conditions, the a-labelings of these graphs can be transformed into harmonious labelings. We also present a closed formula for the number of 2-link fences examined here.

Keywords

Main Subjects

References

[1] 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., 34 (1984), 205–211.
[2] C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl. 34 (2002), 17–26.
[3] C. Barrientos and S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015), 73–83.
[4] C. Barrientos and S. Minion, Counting and labeling grid related graphs, Electron. J. Graph Theory Appl. 7 (2019), no. 2, 349–363.
[5] G. Chartrand and L. Lesniak, Graphs & digraphs, 4th ed., CRC Press, Boca Raton, 2005.
[6] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, On edge-magic labelings of certain disjoint unions of graphs, Australas. J. Combin. 32 (2005), 225–242.
[7] J. A. Gallian, A survey: recent results, conjectures and open problems on labeling graphs, J. Graph Theory 13 (1989), 491–504.
[8] , A dynamic survey of graph labeling, Electron. J. Combin. (2020).
[9] S. W. Golomb, Polyominoes: Puzzles, patterns, problems, and packings, Princeton University Press, 1996.
[10] R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Methods, 1 (1980), 382–404.
[11] D. Jungreis and M. Reid, Labeling grids, Ars Combin. 34 (1992), 167–182.
[12] S. C. López and F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: Relations and techniques, Springer, Cham, 2017.
[13] M. Maheo and H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982), 181–192.
[14] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach (1967), 349–355.
[15] , Labelling snakes, Ars Combin. 3 (1977), 67–74.
[16] A. Rosa and J. Širáň,  Bipartite labelings of trees and the gracesize, J. Graph Theory 19 (1995), 201–215.
[17] P. J. Slater, On k-graceful graphs, Proc. of the 13th S.E. Conf. on Combinatorics, Graph Theory and Computing (1982), 53–57.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 77-101

Files

Share

How to cite

Statistics