Research Article
BibTex RIS Cite

On the generation of alpha graphs

Year 2022, Volume: 9 Issue: 2, 31 - 43, 13.05.2022
https://doi.org/10.13069/jacodesmath.1111733

Abstract

Graceful labelings constitute one of the classical subjects in the area of graph labelings; among them, the most restrictive type are those called {$\alpha$}-labelings. In this work, we explore new techniques to generate {$\alpha$}-labeled graphs, such as vertex and edge duplications, replications of the entire graph, and $k$-vertex amalgamations. We prove that for some families of graphs, it is possible to duplicate several vertices or edges. Using $k$-vertex amalgamations we obtain an {$\alpha$}-labeling of a graph that can be decomposed into multiple copies of a given {$\alpha$}-labeled graph as well as a robust family of irregular grids that can {$\alpha$}-labeled.

References

  • [1] C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.
  • [2] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.
  • [3] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.
  • [4] C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47.
  • [5] G. Chartrand, L. Lesniak, Graphs & digraphs, 4th Edition. CRC Press, Boca Raton (2005).
  • [6] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6.
  • [7] S. W. Golomb, How to number a graph, R. C. Read (Editor), Graph theory and computing, Academic Press, New York (1972) 23-37.
  • [8] D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.
  • [9] V. J. Kaneria, S. K. Vaidya, G. V. Ghodasara, S. Srivastav, Some classes of disconnected graceful graphs, Proc. First Internat. Conf. Emerging Technologies and Appl. Engin. Tech. Sci. (2008) 1050–1056.
  • [10] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.
  • [11] S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017).
  • [12] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982) 181–192.
  • [13] G. Ringel, Problem 25, in: Theory of graphs and its applications, Proc. Symposium Smolenice 1963, Czech. Acad. Sci., Prague, Czech. (1964) 162. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966)
  • [14] A. Rosa, On certain valuations of the vertices of a graph, theory of graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach NY and Dunod Paris (1967) 349–355.
  • [15] A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.
  • [16] A. Rosa, J. Širán, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.
  • [17] G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064.
  • [18] P. J. Slater, On k-graceful graphs, Proc. of the 13th S. E. Conf. on Combinatorics, Graph Theory and Computing (1982) 53–57.
  • [19] B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.
Year 2022, Volume: 9 Issue: 2, 31 - 43, 13.05.2022
https://doi.org/10.13069/jacodesmath.1111733

Abstract

References

  • [1] C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.
  • [2] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.
  • [3] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.
  • [4] C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47.
  • [5] G. Chartrand, L. Lesniak, Graphs & digraphs, 4th Edition. CRC Press, Boca Raton (2005).
  • [6] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6.
  • [7] S. W. Golomb, How to number a graph, R. C. Read (Editor), Graph theory and computing, Academic Press, New York (1972) 23-37.
  • [8] D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.
  • [9] V. J. Kaneria, S. K. Vaidya, G. V. Ghodasara, S. Srivastav, Some classes of disconnected graceful graphs, Proc. First Internat. Conf. Emerging Technologies and Appl. Engin. Tech. Sci. (2008) 1050–1056.
  • [10] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.
  • [11] S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017).
  • [12] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982) 181–192.
  • [13] G. Ringel, Problem 25, in: Theory of graphs and its applications, Proc. Symposium Smolenice 1963, Czech. Acad. Sci., Prague, Czech. (1964) 162. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966)
  • [14] A. Rosa, On certain valuations of the vertices of a graph, theory of graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach NY and Dunod Paris (1967) 349–355.
  • [15] A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.
  • [16] A. Rosa, J. Širán, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.
  • [17] G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064.
  • [18] P. J. Slater, On k-graceful graphs, Proc. of the 13th S. E. Conf. on Combinatorics, Graph Theory and Computing (1982) 53–57.
  • [19] B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.
There are 19 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Christian Barrientos This is me

Publication Date May 13, 2022
Published in Issue Year 2022 Volume: 9 Issue: 2

Cite

APA Barrientos, C. (2022). On the generation of alpha graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 9(2), 31-43. https://doi.org/10.13069/jacodesmath.1111733
AMA Barrientos C. On the generation of alpha graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. May 2022;9(2):31-43. doi:10.13069/jacodesmath.1111733
Chicago Barrientos, Christian. “On the Generation of Alpha Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 9, no. 2 (May 2022): 31-43. https://doi.org/10.13069/jacodesmath.1111733.
EndNote Barrientos C (May 1, 2022) On the generation of alpha graphs. Journal of Algebra Combinatorics Discrete Structures and Applications 9 2 31–43.
IEEE C. Barrientos, “On the generation of alpha graphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 2, pp. 31–43, 2022, doi: 10.13069/jacodesmath.1111733.
ISNAD Barrientos, Christian. “On the Generation of Alpha Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 9/2 (May 2022), 31-43. https://doi.org/10.13069/jacodesmath.1111733.
JAMA Barrientos C. On the generation of alpha graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2022;9:31–43.
MLA Barrientos, Christian. “On the Generation of Alpha Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 2, 2022, pp. 31-43, doi:10.13069/jacodesmath.1111733.
Vancouver Barrientos C. On the generation of alpha graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2022;9(2):31-43.