Research Article
BibTex RIS Cite
Year 2019, , 1 - 10, 20.03.2019
https://doi.org/10.32323/ujma.520682

Abstract

References

  • [1] 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.
  • [2] G. S. Bloom, S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE, 65 (1977), 562-570.
  • [3] G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, In Theory and Applications of Graphs, Lecture Notes in Math., 642, Springer-Verlag,New York, 1978, 53-65.
  • [4] L. Brankovic, I. M. Wanless, Graceful labelling: State of the art, applications and future directions, Math Comput. Sci., 5 (2011), 11-20.
  • [5] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin., 13 (1982), 181-192.
  • [6] P. J. Slater, On k-graceful graphs, Proc. of the 13th S.E. Conf. on Combinatorics, Graph Theory and Computing, (1982), 53-57.
  • [7] C. Barrientos, Difference Vertex Labelings, Ph.D. Thesis, Universitat Politecnica de Catalunya, Barcelona, 2004.
  • [8] G. Chartrand, L. Lesniak, Graphs & Digraphs, 2nd ed. Wadsworth & Brooks/Cole, Monterey, 1986.
  • [9] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 21(#DS6), 2018.
  • [10] C. Barrientos, S. Minion, Counting and labeling grid related graphs, preprint.
  • [11] V. Jovovic, https://oeis.org/A002620, 2000.
  • [12] C. Barrientos, https://oeis.org/A152271, 2019.
  • [13] D. Morgan, All lobsters with perfect matchings are graceful, Electron. Notes Discrete Math., 11 (2002), 6 pages.
  • [14] J. C. Bermond, Graceful graphs, radio antennae and French windmills, Graph Theory and Combinatorics, Pitman, London, 1979, 18-37.
  • [15] R. Stanton, C. Zarnke, Labeling of balanced trees, Proc. 4th Southeast Conf. Combin., Graph Theory and Combinatorics, (1973), 479-495.
  • [16] M. Burzio, G. Ferrarese, The subdivision graph of a graceful tree is a graceful tree, Discrete Math., 181 (1998) 275-281.
  • [17] J. G. Wang, D. J. Jin, X.-G Lu, D. Zhang, The gracefulness of a class of lobster trees, Math. Comput. Modelling, 20 (1994), 105-110.
  • [18] D. Mishra, A. C. Panda, Some new family of graceful lobsters, Adv. Appl. Discrete Math., 14(1) (2014), 1-24.
  • [19] D. Mishra, P. Panigrahi, Graceful lobsters obtained by component moving of diameter four trees, Comput. Math. Appl., 50 (2005), 367-380.
  • [20] D. Mishra, P. Panigrahi, Some graceful lobsters with all three types of branches incident on the vertices of the central path, Comput. Math. Appl., 56 (2008), 1382-1394.
  • [21] D. Mishra, P. Panigrahi, Some new classes of graceful lobsters obtained from diameter four trees, Math. Bohem., 135 (2010), 257-278.
  • [22] E. Krop, Lobsters with an almost perfect matching are graceful, Bull. Inst. Combin. Appl., 74 (2015), 21-24.
  • [23] C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002), 17-26.

Special Graceful Labelings of Irregular Fences and Lobsters

Year 2019, , 1 - 10, 20.03.2019
https://doi.org/10.32323/ujma.520682

Abstract

Irregular fences are subgraphs of $P_m \times P_n$ formed with $m$ copies of $P_n$ in such a way that two consecutive copies of $P_n$ are connected with one or two edges; if two edges are used, then they are located in levels separated an odd number of units. We prove here that any of these fences admits a special kind of graceful labeling, called $\alpha$-labeling. We show that there is a huge variety of this type of fences presenting a closed formula to determine the number of them that can be built on the grid $[1,m] \times [1, n]$. If only one edge is used to connect any pair of consecutive copies of $P_n$, the resulting graph is a tree. We use the $\alpha$-labelings of this type of fences to construct and label a subfamily of lobsters, partially answering the long standing conjecture of Bermond that states that all lobsters are graceful. The final labeling of the lobsters presented here is not only graceful, it is an $\alpha$-labeling, therefore they can be used to produce new graceful trees.

References

  • [1] 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.
  • [2] G. S. Bloom, S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE, 65 (1977), 562-570.
  • [3] G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, In Theory and Applications of Graphs, Lecture Notes in Math., 642, Springer-Verlag,New York, 1978, 53-65.
  • [4] L. Brankovic, I. M. Wanless, Graceful labelling: State of the art, applications and future directions, Math Comput. Sci., 5 (2011), 11-20.
  • [5] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin., 13 (1982), 181-192.
  • [6] P. J. Slater, On k-graceful graphs, Proc. of the 13th S.E. Conf. on Combinatorics, Graph Theory and Computing, (1982), 53-57.
  • [7] C. Barrientos, Difference Vertex Labelings, Ph.D. Thesis, Universitat Politecnica de Catalunya, Barcelona, 2004.
  • [8] G. Chartrand, L. Lesniak, Graphs & Digraphs, 2nd ed. Wadsworth & Brooks/Cole, Monterey, 1986.
  • [9] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 21(#DS6), 2018.
  • [10] C. Barrientos, S. Minion, Counting and labeling grid related graphs, preprint.
  • [11] V. Jovovic, https://oeis.org/A002620, 2000.
  • [12] C. Barrientos, https://oeis.org/A152271, 2019.
  • [13] D. Morgan, All lobsters with perfect matchings are graceful, Electron. Notes Discrete Math., 11 (2002), 6 pages.
  • [14] J. C. Bermond, Graceful graphs, radio antennae and French windmills, Graph Theory and Combinatorics, Pitman, London, 1979, 18-37.
  • [15] R. Stanton, C. Zarnke, Labeling of balanced trees, Proc. 4th Southeast Conf. Combin., Graph Theory and Combinatorics, (1973), 479-495.
  • [16] M. Burzio, G. Ferrarese, The subdivision graph of a graceful tree is a graceful tree, Discrete Math., 181 (1998) 275-281.
  • [17] J. G. Wang, D. J. Jin, X.-G Lu, D. Zhang, The gracefulness of a class of lobster trees, Math. Comput. Modelling, 20 (1994), 105-110.
  • [18] D. Mishra, A. C. Panda, Some new family of graceful lobsters, Adv. Appl. Discrete Math., 14(1) (2014), 1-24.
  • [19] D. Mishra, P. Panigrahi, Graceful lobsters obtained by component moving of diameter four trees, Comput. Math. Appl., 50 (2005), 367-380.
  • [20] D. Mishra, P. Panigrahi, Some graceful lobsters with all three types of branches incident on the vertices of the central path, Comput. Math. Appl., 56 (2008), 1382-1394.
  • [21] D. Mishra, P. Panigrahi, Some new classes of graceful lobsters obtained from diameter four trees, Math. Bohem., 135 (2010), 257-278.
  • [22] E. Krop, Lobsters with an almost perfect matching are graceful, Bull. Inst. Combin. Appl., 74 (2015), 21-24.
  • [23] C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002), 17-26.
There are 23 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Articles
Authors

Christian Barrientos 0000-0003-2838-8687

Publication Date March 20, 2019
Submission Date February 1, 2019
Acceptance Date March 6, 2019
Published in Issue Year 2019

Cite

APA Barrientos, C. (2019). Special Graceful Labelings of Irregular Fences and Lobsters. Universal Journal of Mathematics and Applications, 2(1), 1-10. https://doi.org/10.32323/ujma.520682
AMA Barrientos C. Special Graceful Labelings of Irregular Fences and Lobsters. Univ. J. Math. Appl. March 2019;2(1):1-10. doi:10.32323/ujma.520682
Chicago Barrientos, Christian. “Special Graceful Labelings of Irregular Fences and Lobsters”. Universal Journal of Mathematics and Applications 2, no. 1 (March 2019): 1-10. https://doi.org/10.32323/ujma.520682.
EndNote Barrientos C (March 1, 2019) Special Graceful Labelings of Irregular Fences and Lobsters. Universal Journal of Mathematics and Applications 2 1 1–10.
IEEE C. Barrientos, “Special Graceful Labelings of Irregular Fences and Lobsters”, Univ. J. Math. Appl., vol. 2, no. 1, pp. 1–10, 2019, doi: 10.32323/ujma.520682.
ISNAD Barrientos, Christian. “Special Graceful Labelings of Irregular Fences and Lobsters”. Universal Journal of Mathematics and Applications 2/1 (March 2019), 1-10. https://doi.org/10.32323/ujma.520682.
JAMA Barrientos C. Special Graceful Labelings of Irregular Fences and Lobsters. Univ. J. Math. Appl. 2019;2:1–10.
MLA Barrientos, Christian. “Special Graceful Labelings of Irregular Fences and Lobsters”. Universal Journal of Mathematics and Applications, vol. 2, no. 1, 2019, pp. 1-10, doi:10.32323/ujma.520682.
Vancouver Barrientos C. Special Graceful Labelings of Irregular Fences and Lobsters. Univ. J. Math. Appl. 2019;2(1):1-10.

 23181

Universal Journal of Mathematics and Applications 

29207              

Creative Commons License  The published articles in UJMA are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.