Special Graceful Labelings of Irregular Fences and Lobsters

Authors : Christian Barrientos

Pages : 1-10

Doi:10.32323/ujma.520682

View : 40 | Download : 9

Publication Date : 2019-03-20

Article Type : Research Paper

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.
Keywords : Fence, Graceful labelling, Lobster

ORIGINAL ARTICLE URL