{'fraction_non_alphanumeric': 0.044134078212290505, 'fraction_numerical': 0.017398244213886672, 'mean_word_length': 4.21039501039501, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Graceful Algebraic Function Labelling of Rooted Symmetric Trees

Let T=(V,E) be a tree with vertex set V and edge set E. A graceful labelling f of T is an injective function f from V into {0, 1, ..., |E|} such that if edge uv is assigned the label g(uv)=|f(u)-f(v)| then the function g from E into {1, ..., |E|} is also injective (that is all edge labels are distinct). A rooted symmetric tree is a tree in which all vertices at the same level from root vertex have the same degree. It has been known since 1979 that rooted symmetric trees are graceful. However, the proofs that have been presented for this fact are either indirect inductive proofs or algorithmic descriptive proofs showing the many separate steps involved in labelling the vertices. Given a rooted symmetric tree, we find a graceful labelling f of T in the form of a direct algebraic function that algebraically maps each vertex of T to a unique label. Interestingly, f turns out to be a generalisation of the way a path is canonically gracefully labelled as algorithmically described by A. Rosa who is a pioneer in this field of research. The algebraic function that defines the graceful labelling is used to show that a class of rooted symmetric trees that contains the class of binomial trees has weakly {\alpha}-labelling and it can provide a concise practical, computational way of producing graceful labelling of large rooted symmetric trees in, relatively, minimal time.


Introduction
A graceful labelling of a tree T = (V, E) with vertex set V and edge set E, is an injective function f : V → {0, 1, …, |E|} such that if edge uv is assigned the label g(uv)=|f(u)-f(v)| then the function g : E → {1, …, |E|} is also injective (that is all edge labels are distinct) . Several graph labelling schemes were first introduced by A. Rosa (Rosa, 1967) as a means of attacking the Ringel Conjecture that the complete graph K2n+1 can be decomposed into 2n+1 isomorphic trees each on n edges (Ringel, 1963). Although A. Rosa introduced four different labelling schemes of graphs that can lead to the proof of the Ringel conjecture, nevertheless b-valuations, or graceful labelings, as were subsequently called by Golomb (1972), caught the attention and efforts of the largest part of researchers resulting in a vast reservoir of papers about the subject.
For the purpose of this paper we also define an α-labelling of a tree T to be a graceful labelling with the additional property that there is a positive integer k such that for any edge xy either f(x) £ k < f(y) or f(y) £ k < f(x). (Gallian, Prout, & Winters, 1992) relaxed the definition of αlabelling and defined a weakly α-labelling to be a graceful labelling with the additional condition that there is a positive integer k such that for each edge xy, either f(x) £ k £ f(y) or f(y) £ k £ f(x). Researchers aimed to prove that all trees are graceful. This conjecture is known as the Ringel-Kotzig conjecture or the graceful tree conjecture (GTC) and despite the vast reservoir of papers that have been produced, it remains one of the most famous unsettled conjectures in graph theory.
The vast reservoir of papers that have been produced about graceful labelings, mostly exploit specific properties of some families of graphs as tools to prove that graphs belonging to these families are graceful. However, unfortunately, none of the techniques used so far are able to resolve the GTC. A list of families of trees that have been proved to be graceful can be found in almost every paper that has been written about the subject (See for example, (Luiz, Campos, & Richter, 2019;Rofa, 2021;Superdock, 2014;Wang, Yang, Hsu, & Cheng, 2015) and a detailed list of results is found in the dynamics survey Gallian (2018). As this paper is about rooted symmetric trees, we focus our literature review to this particular family of trees.
A rooted symmetric tree T is a rooted tree in which the degrees of all vertices at the same level or distance from the root vertex are equal. Figure 1 shows a rooted symmetric tree with root vertex v and seven levels including the root vertex in level 1. Rooted symmetric trees were repeatedly proved to be graceful by Bermond and Sotteau (Bermond & Sotteau, 1976) using G-designs, by Poljak and Sura (S. Poljak & Sˆura, 1982) and Robeva (Robeva, 2011) using algorithmic approaches and by Sandy et. al (Sandy, Rizal, Manurung, & Sugeng, 2018) using adjacency matrices and induction. However, all proofs are either inductive or algorithmic with many separate steps. In this paper we find a graceful labelling of rooted symmetric trees in the form of a direct algebraic function that maps each vertex of T to a unique label. The advantage of having such a direct functional proof lies in facilitating the production of graceful labellings of 'large' rooted symmetric trees in a computational way and in, relatively, minimal time. Furthermore, the graceful function that is found turns out to be a generalisation of the way a path is 'canonically' gracefully labelled as was algorithmically described by A. Rosa (Rosa, 1967). Notice that a path is a special type of a rooted symmetric tee. Therefore, from this point of view the result that is achieved in this paper can be considered as capturing Rosa's Algorithmic method for labelling paths in an algebraic way and generalising the result to include rooted symmetric trees. Figure 1(A) shows a graceful labelling of a 7-level multibranched rooted symmetric trees and Figure 1(B) shows the canonical algorithmic way of labelling a path (Which is a special case of a rooted symmetric tree) discovered by A. Rosa. In this paper we will show that both labellings can be derived through the similar algebraic functions.  Figure 1 (A) Graceful labelling of a symmetric rooted tree with 7 levels (Including root vertex level).
(B) Canonical labelling of a path using the algorithmic method by A. Rosa.

Rooted Symmetric Trees: Definitions and Preliminary Results
In this section, we define the terminology and prove some preliminary results that will be required for providing an algebraic definition of a graceful labelling of a rooted symmetric tree (Section 3).
A rooted symmetric tree T is a rooted tree in which the degrees of all vertices at the same level are equal. Therefore, a rooted symmetric tree with q levels (level 1 to level q where level 1 contains root vertex v only) can be described by giving the constant degree at each level. For 1£ i£q, let ki be the constant 'daughter' degree of each vertex at level i, that is, the number of vertices at level i+1 that are adjacent to a vertex at level i. Notice that vertices of the last level, that is level q, are not adjacent to any 'daughter' vertices, hence kq=0. We call the sequence S = (k1, k2, …, kq-1) the daughter degree sequence of T and it, up to isomorphism totally identifies T. Label the kr daughter vertices of each vertex v at an arbitrary level, say level r, from left to right, by the numbers 0, 1, …, kr -1 (not to be confused by the vertex labels of a graceful labelling of T). This labelling produces an embedding of T in which every vertex (except root vertex) is uniquely determined by a sequence of edge labels (not to be confused with the edge labels induced by a graceful labelling of T). For example, figure 2 shows a rooted symmetric tree with root vertex v0 and degree sequence (k1 = 2, k2 = 3, k3 = 4), in which vertices v2, v5, and v32 are each uniquely represented by the edge sequences (1), (0,2), and (1,2,3), respectively. This identification of a vertex by a unique sequence of edge labels (the edges of the unique path that connects root vertex with the particular vertex that needs to be identified) is going to be used in algebraically defining the graceful labelling, f, of T. The next step is to find algebraic expressions for the number of vertices of the rooted, symmetric subtree having its root vertex at any given level, say level i between 1 and q, inclusive. We call this number the i th level vertex size and denote it by hi. For example, in figure 1, h2 denotes the 2 nd level vertex size and is equal to the number of vertices of the rooted symmetric sub-tree with root vertex v2 (or v1). Using a simple counting technique, h2 is counted as 1+3+3(4) = 16 (Remember, this tree has a daughter degree sequence (k1=2, k2=3, k3=4). The following Lemma gives the level vertex size at any given level. The Lemma is easy to see by using the same counting technique that was used to find h2 above. Lemma 1. For 1£ i £q-1, we have hi = 1 + ki + kiki+1 + . . . + kiki+1 . . .kq-1 and hq = 1 Notice that h1=|V| and hq is the number of vertices of the rooted symmetric tree having its root at the last level, which is a rooted symmetric tree consisting of the root vertex only, thus hq = 1.
The following Corollary gives a recursive relation between two consecutive level vertex sizes Corollary 1. For i between 1 and q-1, inclusive, we have, hi+1 = Proof. Follows directly from Lemma 1. (It is useful for the reader to intuitively understand this formula by applying it to the rooted symmetric tree in figure 1). Now, are in position to present an algebraic definition of a graceful labelling of a rooted symmetric tree. We do this in the following section.

Main Result: Algebraic Definition of a Graceful Labelling of Rooted Symmetric Trees.
As is the case throughout this paper, let T be a rooted symmetric tree with daughter degree sequence (k1, k1, …, kq-1) and root vertex v0. Then using the set up that is described in the previous section, a vertex v at level r (except for the root vertex) is uniquely identified by the sequence of edge labels say (x1, x2, …, xr-1) of the edges that compose the unique path between the root vertex v0 and vertex v. (See previous section for details and examples). We have the following main theorem. . , if r is even 3) ( ) = # ℎ . + . ℎ / +. . . + 2"# ℎ 2 + 2"# . , if r is odd. is a graceful labelling of the rooted symmetric tree T.
Theorem 1 is proved by showing that the functions f and the function g : E → {1, …, |E|} which is induced by f are both injective functions. but before doing that we demonstrate how Theorem 1 works in the following example. For the remainder of this paper f will be the function specified by theorem 1.
Repeat until a remainder of 0 is obtained and set f -1 (m) to be the unique vertex identified by the sequence (e1, e2, e3, …) if the vertex belongs an even level and (q1, q2, q3, …), if the vertex belongs to an odd level. End of Algorithm 1.
Note that algorithm 1 assigns a unique vertex to each element in the domain of f -1 and that it must terminate because in subsequent step, the remainder from the previous step is reduced by 1. This proves that f -1 is a well-defined function and therefore, the function f is an injective function which is one of the first requirements for f to be a graceful labelling of T. A similar, but slightly more complicated algorithm, can show that g -1 is a well-defined function. Therefore, f is a graceful labelling of T.

End of Proof of Theorem 1.
We illustrate Algorithm 1 in the following example.

Example 2
Consider the rooted symmetric tree T in figures 2 and the graceful labelling of T in figure 3. a) Applying Algorithm 1 to vertex label m = 32 from figure 3 results in f -1 (32) = (0) which correctly identifies the corresponding vertex v1 in figure 2. b) Applying Algorithm 1 to vertex label m = 10 from figure 3 results in f -1 (10) = (1,1,0) which correctly identifies the corresponding vertex v25 in figure 2.
Next, we will show that the canonical algorithmic graceful labelling method that was applied by A. Rosa to gracefully label paths can be captured by an algebraic function according to theorem 1. To clarify the concept, consider path P on 7 vertices, shown in figure 1(B). P can be thought of as a rooted symmetric tree with root vertex v (end vertex shown in the figure). By finding the level vertex sizes of P and applying the corresponding function f of theorem 1, we get the same labelling that could be found by using the algorithmic method of A. Rosa.
Our final result is to prove that the function f of theorem 1 is a weakly α-labelling of any rooted symmetric tree with daughter degree sequences (k1, k2, …), where k1 = 2 Lemma 1. Let T be a rooted symmetric tree with daughter degree sequence (k1, k2, …), where k1 = 2, then T has a weakly α-labelling.
Proof. The proof follows from corollary 1 as a binary tree is a rooted symmetric tree with daughter degree sequence (2, 2, …).