Expanding graceful trees

I Nengah Suparta, I Dewa M. Agus Ariawan

Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Pendidikan Ganesha, Jalan Udayana 11 Singaraja-Bali, Indonesia

nengah.suparta@undiksha.ac.id, iddeagus@gmail.com

Two methods for expanding graceful trees are introduced. In constructing a larger graceful trees, these methods are based on a collection of certain graceful trees and one graceful tree as the core of the produced graceful tree.

Keywords: graceful labeling, graceful tree, interlaced tree Mathematics Subject Classification : 05C12, 05C78

DOI: 10.5614/ejgta.2020.8.2.2

1. Introduction

All graphs we encounter in this paper are finite undirected simple graph. Let G(V, E) denote the graph G with vertex set V (G) and edge set E(G). Labeling on a graph is an assignment of a nonnegative integer on each vertex or each edge, or both of the graph under a certain condition. Graph labeling has found its application in coding theory, X-ray crystallography, radar and missile guidance [1]. If X is a set, let us denote by |X| the number of elements in the set X. A graceful labelling of a graph G is an injective function f : V (G) → {0, 1, . . . , |E(G)|} which induces a bijective function f 0 : E(G) → {1, 2, . . . , |E(G)|} defined by f 0 (uv) = |f(u) − f(v)| for every uv ∈ E(G). If a graph G has a graceful labeling then G is called graceful. A graceful labeling is called α-labeling if we can find an integer k such that for every edge uv ∈ G we have f(u) ≤ k < f(v) or f(v) ≤ k < f(u). Ringel and Kotzig in 1960s gave a conjecture which was reformulated by Rosa 1967 (see [2]) as "every tree has a graceful labelling". This conjecture

Received: 26 September 2019, Revised: 17 February 2020, Accepted: 25 March 2020.

is frequently called The Graceful Tree Conjecture or shortly as GTC. Since then many research results have been formulated which focus on graceful tree problems, and many classes of trees have already been proved to be graceful. For extensive survey of these results one may consult to Gallian [2].

In this paper we will introduce some method of constructing larger graceful trees by combining or identifying smaller graceful trees. The method uses one graceful tree T of m points as a core and a collection of m graceful trees \(T_i\), \(1 \le i \le m\). In some case, this technique needs a specific core tree which is constructed using m paths of two points. Denote by \(T * \Gamma(m)\) the tree which is obtained by identifying each vertex of T with exactly one certain vertex of every tree in \(\Gamma(m)\). Using this kind of method Stanton and Zarnke in [8] and Koh, Rogers and Tan in [3, 4, 5, 6] had produced some classes of graceful trees. Here we generalized some part of their method to obtain some new classes of graceful trees which are not yet covered in [3, 4, 5, 6, 7, 8].

2. Result

From now on, if G is a graph, then the set of all vertex labels of G will be denoted by L(V(G)). Let T be a tree and \(v \in V(T)\). The parity set P(v) of the vertex v in a tree T is the set of vertices, including the vertex v, which are at even distance from v. If T has graceful labeling f then the vertex b of T for which f(b) = 0 is called the base of T. A graceful tree T is called interlaced if \(L(P(b)) = \{0,1,2,\ldots,|P(b)|-1\}\). It is easy to see that an interlaced tree has \(\alpha\)-labeling with k = |P(b)| - 1. For this reason, one also calls interlaced tree as \(\alpha\)-tree. Let \(\Gamma(m) = \{T_1, T_2, \ldots, T_m\}\) be a collection of m disjoint graceful trees, where \(T_i\) is with \(n_i\) vertices. For the sake of efficiency, if \(T_i\) is a tree of index i with label function \(f_i\), through out this paper we will denote by \(P_i\) for \(P(b_i)\), with \(f_i(b_i) = 0\), \(|P_i| = p_i\), \(P_i^c\) for the complement of \(P_i\), and \(|P_i^c| = p_i^*\). It is clear that \(p_i^* = n_i - p_i\). Furthermore, let \(N(a) = \sum_{i=1}^a n_i\) for some positive integer a, and for \(k, 0 \le k \le m\), let \(s(k) = \sum_{i=1}^k p_i\) and \(s(k)^* = \sum_{i=1}^k p_i^*\), with s(0) = 0 and \(s(0)^* = 0\).

Consider the collection \(\Gamma(m)\) as a graph of m components \(T_1, T_2, \ldots, T_m\). Following the terminology of Koh, Rogers, and Tan in [5], we will call \(\Gamma(m)\) a compatible collection if there exists a labeling function f for \(\Gamma(m)\) such that all vertex labels of \(\Gamma(m)\) are \(\alpha, 0 \le \alpha \le N(m) - 1\), and the edge labels of \(\Gamma(m)\) are \(\beta, 1 \le \beta \le N(m) - 1\), with m-1 missing edge labels. If such the function f exists, then f is called a compatible labeling of \(\Gamma(m)\).

The following lemma is due to Koh, Rogers, and Tan in [5] with a slightly different formulation.

Lemma 2.1. If \(\Gamma(m)\) is a collection of m interlaced trees \(T_i\), \(1 \le i \le m\), then \(\Gamma(m)\) is compatible collection with m-1 missing edge labels N(m)-N(m-i), \(i=1,2,\ldots,m-1\).

Proof. Let \(f_i\) be the graceful labeling of tree \(T_i\). Inductively we can show using the following label function

\[g(v) = \begin{cases} f_i(v) + s(i-1) & \text{if } v \in P \\ f_i(v) + N(m) - s(i-1)^* - n_i & \text{if } v \in P^c \end{cases}\] (1)

that the vertex labels of \(\Gamma(m)\) will have the following properties:

1. \[L(P) = \{0, 1, \dots, s(m) - 1\},\\]

2. \[L(P^c) = \{s(m), s(m) + 1, \dots, N(m) - 1\},\\]

where \(P = \bigcup_{i=1}^m P_i\) and \(P^c = \bigcup_{i=1}^m P_i^c\).

Based on Eq. (1), for every edge uv in \(T_i\), with \(1 \le i \le m\), we have that its label is equal to \(|g(u) - g(v)| = |f_i(u) - f_i(v)| + N(m) - N(i)\). From these new labels, we can immediately see that the missing edge labels in the resulting compatible collection \(\Gamma(m)\) are N(m) - N(m-i), \(i = 1, \ldots, m-1\).

Example 1 In Figure 1 we show a collection \(\Gamma(6)\) of interlaced trees \(T_i, 1 \le i \le 6\). After relabeling \(\Gamma(6)\) using the function in Eq. (1), then we have a compatible labeling as in Figure 2. In this example we have m=6 and \(n_i=8, 1\le i\le 6\). Thus, according to Lemma 2.1, the 5 missing edge labels are 8, 16, 24, 32, and 40 as we can see also from Figure 2.

Figure 1. A collection of interlaced trees \(T_i\), \(1 \le i \le 6\).

Lemma 2.2. Let \(\Gamma(m)\) be a collection of interlaced trees \(T_i\), \(1 \le i \le m\), where each \(T_i\) has n vertices. Then for some \(r \in \{0, 1, \ldots, n-1\}\), for every \(i = 1, 2, \ldots, m\), \(L(V(T_i))\) contains exactly one label of the form nj + r for every \(j = 0, 1, \ldots m-1\).

Proof. Take some r in \(\{0, 1, \ldots, n-1\}\). Assume that for some \(i, 1 \le i \le m, nj+r, nk+r \in L(V(T_i))\) with \(j \ne k\) and \(0 \le j, k \le m-1\). First, we will show that labels nj+r and nk+r both should be neither in \(L(P_i)\) nor in \(L(P_i^c)\). Since \(T_i\) is interlaced, we can infer that the vertex labels in \(P_i\) and in \(P_i^c\) constitute \(p_i\) and \(p_i^*\) non negative consecutive integers, respectively. On the other

Figure 2. A compatible labeling of \(\Gamma(6)\).

side \(|(nj+r)-(nk+r)|=cn>\max\{p_i,p_i^*\}\) for some positive integer c. This indicates that the labels nj+r and nk+r cannot be both in \(L(P_i)\) nor in \(L(P_i^c)\).

Next we will show that for every \(i, T_i\) contains exactly one label of the form nl+r for some positive integer \(l, 0 \le l \le m-1\). In other words, \(nj+r \in L(P_i)\) if and only if \(nk+r \not\in L(P_i^c)\). Without lost of generality, assume that nj+r < nk+r. The number of vertex labels which are less than nj+r and greater than nk+r in \(L(V(\Gamma(i)))\) are nj+r and N(m)-1-nk-r=mn-nk-1-r, respectively. This implies that the total labels which have been used for vertices of \(\Gamma(i)\) is mn+nj-nk-1=dn-1 with d=m+j-k.

On the other side, since each \(T_j\) has n vertices for every j < i, we may infer based on the way of labeling \(\Gamma(i)\), that among dn - 1 labels, n - 1 labels are either for vertices of \(T_{i-1}\) or of \(T_i\).

For the previous case, say that those n-1 labels all for \(T_{i-1}\). This means that \(T_{i-1}\) misses only one vertex label, that is either nj+r or nk+r. But this contradicts the assumption that nj+r and nk+r are already in \(T_i\).

For the later case, let those n-1 labels all be for the vertices of \(T_i\). These labels are different from nj+r and nk+r. This implies that \(T_i\) has n+1 vertex labels including the labels nj+r and nk+r, which contradicts the fact that \(T_i\) has only n vertices.

Thus, in any case we may conclude that either nj + r or nk + r is in \(L(V(T_i))\).

Moreover, for every \(j, 0 \le j \le m-1\), and for every \(r, 0 \le r \le n-1\), we can immediately see that \(nj+r \in \{0,1,\ldots,mn-1\} = L(V(\Gamma(m)))\). For some fixed r, there are m labels of the form nj+r in \(\Gamma(m)\). Since for every \(i,1 \le i \le m\), \(L(V(T_i))\) consists of maximum one label of the

form nj + r, we may conclude that L(V (Ti)) consists of exactly one label of the form nj + r.

Now, we will define a construction to generate a larger new graceful tree which is obtained by arranging a tree T and a collection Γ(m). Denote by T ∗ Γ(m) the tree which is obtained by identifying each vertex of T with exactly one vertex of each tree in Γ(m) of the same label after relabeling. In the sequel, the tree T will be called the core tree for the T ∗ Γ(m) construction.

Theorem 2.1. Let T be a graceful tree of m vertices. If Γ(m) is a collection of interlaced trees Tⁱ , 1 ≤ i ≤ m, where each Tⁱ has n vertices, then T ∗ Γ(m) is graceful.

Proof. Let f be a graceful labeling of T. For some r, 0 ≤ r < n, define a relabeling function f ∗ for T as follows:

\[f^*(v) = f(v)n + r, \text{ if } v \in T.\] (2)

Observe that the new vertex labels of T are nj + r for every j ∈ {0, 1, . . . , n − 1}. Since T is graceful, then based on the function f ∗ , the set of the new edge labels of T is equal to L(E(T)) = {|f ∗ (u) − f ∗ (v)| : uv ∈ E(T)} = {n, 2n, . . . ,(m − 1)n}. These edge labels, by Lemma 2.1, will complete m − 1 missing labels of Γ(m). Then, by Lemma 2.2, we conclude that T ∗ Γ(m) is graceful.

Figure 3. A graceful tree of 6 vertices.

Example 2 Let T be a graceful tree on six vertices as in Figure 3, and Γ(6) be a compatible collection of interlaced trees where each Tⁱ has 8 vertices as in Figure 2. Then T ∗ Γ(6) is given as in Figure 4.

Now we will introduce a method for constructing graceful graphs, including trees, based on the path of size one. This method has beneficial side in applying the construction technique which will be described soon after this section. A graceful tree which is produced using the method will take its role as the core tree of this graceful construction technique. How the graceful graph is constructed, is implicitly shown in the following theorem.

Theorem 2.2. Let f be the graceful labeling of path P2. For every i, 1 ≤ i ≤ m, we define i functions ¯fi,j , 0 ≤ j ≤ i − 1, as follows:

Figure 4. Graceful tree \(T * \Gamma(6)\).

31

\[\bar{f}_{i,j}(v) = \begin{cases} j, & \text{if } f(v) = 0\\ m+1-(i-j), & \text{if } f(v) = 1 \end{cases}\] (3)

11

Let i be a positive integer, \(1 \le i \le m\), and \(T_i\) be a family of paths \(T_{i,j}\), where j = 0, 1, ..., i - 1. Let G be a graph consisting of m paths \(T_{i,j}\) such that for every i = 1, 2, ..., m, there is precisely one path \(T_{i,j_i}\) for some \(j_i\) and the paths are amalgamated at vertices with identical labels. Then G is graceful.

Proof. By using Eq. (3) we have that the edge labels of G are \(\{|\bar{f}_{i,j}(u) - \bar{f}_{i,j}(v)| : 1 \le i \le m, 0 \le j < i\} = \{m+1-i: i=1,\ldots,m\} = \{1,\ldots,m\}\). Hence, by the construction of G, we may conclude that G is graceful.

Note that using a construction as in Theorem 2.2, we have m! graceful graphs, some of them are graceful trees.

Example 3. We will construct a graph G by using construction as in Theorem 2.2 with \(\bar{T}_i, 1 \le i \le 5\), as in Figure 5. We choose \(T_{1,0}, T_{2,1}, T_{3,1}, T_{4,2}\) and \(T_{5,3}\), each from one \(\bar{T}_i, 1 \le i \le 5\). Then we have a graceful graph G as shown in Figure 6.

So far, all trees in the collection \(\Gamma(m)\) have restriction that the number of their vertices are the same. Now we will introduce another construction based on pairs of trees with possibly different number of vertices respectively.

Figure 5. A family of T¯ i , 1 ≤ i ≤ 5.

Figure 6. An example of Theorem 2.2.

Let \(T_1\) and \(T_2\) be interlaced trees on \(n_1\) and \(n_2\) vertices. If \(p_1 + p_2 = p_1^* + p_2^*\), then \(\{T_1, T_2\}\) is called a supplementary-pair. Now, let \(\Gamma(m)\), m even, be a collection of m interlaced trees where for \(i = \{1, 3, \ldots, m-1\}\), \(\{T_i, T_{i+1}\}\) is a supplementary-pair. Then, by Lemma 2.1, \(\Gamma(m)\) is a compatible collection, and the missing edge labels of \(\Gamma(m)\) are N(m) - N(m-i), \(i = 1, 2, \ldots, m-1\).

Let \(\Gamma(m)\), m=2l for some positive integer l, be a collection of interlaced trees and \(\{T_i, T_{i+1}\}\) for \(i=\{1,3,\ldots,m-1\}\) be a supplementary-pair such that the following properties hold.

• (a) If \(n_1 \ge n_2\) then \(p_{i\equiv 1 \pmod{4}}, p^*_{i\equiv 0 \pmod{4}} > r\) and
• (b) If \(n_1 < n_2\) then \(p_{i \equiv 3 \pmod{4}}, p_{i \equiv 2 \pmod{4}}^* > r\),

with \[n_i = n_1, n_{i+1} = n_2\] and \(r = \lfloor \frac{n_1 - n_2}{2} \rfloor\).

Let \(J=\{1,3,\ldots,m-1\}, K=\{0,2,\ldots,m-2\}, L_1=\{0,1,\ldots,\min\{p_{i\equiv 1(\bmod 4)}-r-1,p_{i\equiv 2(\bmod 4)}^*-1,p_{i\equiv 2(\bmod 4)}^*-1,p_{i\equiv 2(\bmod 4)}^*-r-1\}\}\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Lemma 2.3. Let \(\Gamma(m)\), m=2l for some positive integer l, be a collection of m interlaced trees and \(\{T_i, T_{i+1}\}\) for \(i=\{1,3,\ldots,m-1\}\) be a supplementary-pair such that the conditions (a) and (b) above hold. Then, we can label \(\Gamma(m)\) such that there exists exactly one vertex in each component of \(\Gamma(m)\) which has label \(s_j+w\) or \(t_k+w\) with \(j\in J\), \(k\in K\), and \(w\in L_1\) if \(n_1\geq n_2\) or with \(j\in K\), \(k\in J\) and \(w\in L_2\) if \(n_1< n_2\).

Proof. Since every \(\{T_i, T_{i+1}\}\) for \(i \in \{1, 3, \dots, m-1\}\) is a supplementary-pair, then \(p_i + p_{i+1} = p_i^* + p_{i+1}^* = \frac{n_1 + n_2}{2}\). Based on the way we label the vertices of \(T_i\) as in Eq. (1) in the proof of Lemma 2.1, we can conclude that the vertex labels of \(P_i \bigcup P_{i+1}\) and of \(P_i^c \bigcup P_{i+1}^c\) are \(\frac{n_1 + n_2}{2}\) consecutive non negative integers, respectively. More precisely, we have \(L(P_i \bigcup P_{i+1}) = \{\frac{i-1}{2}(\frac{n_1 + n_2}{2}), \dots, \frac{i+1}{2}(\frac{n_1 + n_2}{2}) - 1\}\), and \(L(P_i^c \bigcup P_{i+1}^c) = \{(m - \frac{i}{2})(\frac{n_1 + n_2}{2}), \dots, (m + \frac{2-i}{2})(\frac{n_1 + n_2}{2}) - 1\}\). It implies that for every \(i, 0 \le i \le m-1\) the label \((\frac{n_1 + n_2}{2})i\) is the label of exactly one vertex of one component of \(\Gamma(m)\). Note that for every \(i \in \{1, 3, \dots, m-1\}\) the label \((\frac{n_1 + n_2}{2})(\frac{i-1}{2}) = \min\{L(P_i)\}\) and for every \(i \in \{2, 4, \dots, m\}\) the label \((\frac{n_1 + n_2}{2})(m - \frac{i}{2}) = \min\{L(P_i^c)\}\).

Observe that \(\{\frac{i-1}{2}; i \equiv 3 \pmod{4}, 1 \leq i \leq m\} \bigcup \{m - \frac{i}{2}; i \equiv 2 \pmod{4}, 1 \leq i \leq m\} = \{1, 3, \dots, m-1\} = J \text{ and } \{\frac{i-1}{2}; i \equiv 1 \pmod{4}, 1 \leq i \leq m\} \bigcup \{m - \frac{i}{2}; i \equiv 0 \pmod{4}, 1 \leq i \leq m\} = \{0, 2, \dots, m-2\} = K.\)

Now we will proceed in two cases:

• (1) \(n_1 \ge n_2\) which implies \(p_{i\equiv 1 \pmod{4}}, p_{i\equiv 0 \pmod{4}}^* > r\), and
• (2) \(n_1 < n_2\) which implies \(p_{i \equiv 3 \pmod{4}}, p_{i \equiv 2 \pmod{4}}^* > r\).

Case (1) Since \(w \in L_1\) is a non negative integer, we have the following facts:

• (i) \(min(L(P_{i\equiv 3(\text{mod }4)}) \le s_j + w \text{ for } j = \frac{i-1}{2},\)
• (ii) \(min(L(P_{i\equiv 2(\text{mod }4)}^c) \le s_j + w \text{ for } j = m \frac{i}{2},\)

(iii) \[min(L(P_{i\equiv 1 \pmod{4}}) \le t_k + w \text{ for } k = \frac{i-1}{2},\]

(iv) \[min(L(P_{i\equiv 0 \pmod{4}}^c) \le t_k + w \text{ for } k = m - \frac{i}{2}.\]

Moreover, since w ∈ L¹ such that w ≤ min{pi≡1(mod 4) − r − 1, p^{∗ i}≡2(mod 4) − 1, pi≡3(mod 4) − 1, p^{∗ i}≡0(mod 4) − r − 1}}, then we have:

(i') \[max(L(P_{i\equiv 3 \pmod{4}}) \ge s_j + w \text{ for } j = \frac{i-1}{2},\]

(ii') \[\max(L(P_{i\equiv 2(\text{mod }4)}^c) \ge s_j + w \text{ for } j = m - \frac{i}{2},\]

(iii') \[max(L(P_{i\equiv 1 \pmod{4}}) \ge t_k + w \text{ for } k = \frac{i-1}{2},\]

(iv') \[\max(L(P_{i\equiv 0 \pmod{4}}^c) \ge t_k + w \text{ for } k = m - \frac{i}{2}.\]

Therefore, by combining (i) and (i 0 ), (ii) and (ii⁰ ) , (iii) and (iii⁰ ), and (iv) and (iv⁰ ) we have successively:

1. \[s_j + w \in L(P_{i \equiv 3 \pmod{4}})\] for \(j = \frac{i-1}{2}\),

2. \[s_j + w \in L(P_{i \equiv 2 \pmod{4}}^c)\] for \(j = m - \frac{i}{2}\),

3. \[t_k + w \in L(P_{i \equiv 1 \pmod{4}})\] for \(k = \frac{i-1}{2}\),

4. \[t_k + w \in L(P_{i \equiv 0 \pmod{4}}^c)\] for \(k = m - \frac{i}{2}\).

From this observation we can conclude that for n¹ ≥ n² we have that sj+w, j ∈ J or tk+w, k ∈ K with w ∈ L¹ is the vertex label of exactly one component of Γ(m).

Case (2)The proof for this case is similar to Case (1).

(i) \[min(L(P_{i\equiv 3 \pmod{4}}) \le t_k + w \text{ for } k = \frac{i-1}{2},\]

(ii) \[min(L(P_{i\equiv 2 \pmod{4}}^c)) \le t_k + w \text{ for } k = m - \frac{i}{2},\]

(iii) \[min(L(P_{i\equiv 1 \pmod{4}}) \le s_j + w \text{ for } j = \frac{i-1}{2},\]

(iv) \[min(L(P_{i\equiv 0 \pmod{4}}^c) \le s_j + w \text{ for } j = m - \frac{i}{2}.\]

Moreover, since w ∈ L² such that w ≤ min{pi≡1(mod 4) − 1, p^{∗ i}≡2(mod 4) − r − 1, pi≡3(mod 4) − r − 1, p^{∗ i}≡0(mod 4) − 1}}, then we have:

(i') \[max(L(P_{i\equiv 3(\text{mod }4)}) \ge t_k + w \text{ for } j = \frac{i-1}{2},\]

(ii') \[\max(L(P_{i\equiv 2 \pmod{4}}^c) \ge t_k + w \text{ for } k = m - \frac{i}{2},\]

(iii') \[max(L(P_{i\equiv 1 \pmod{4}}) \ge s_j + w \text{ for } j = \frac{i-1}{2},\]

(iv') \[\max(L(P_{i\equiv 0 \pmod{4}}^c)) \ge s_j + w \text{ for } j = m - \frac{i}{2}.\]

Therefore, by combining (i) and (i 0 ), (ii) and (ii⁰ ) , (iii) and (iii⁰ ), and (iv) and (iv⁰ ) we have successively:

1. \[t_k + w \in L(P_{i \equiv 3 \pmod{4}})\] for \(k = \frac{i-1}{2}\),

2. \[t_k + w \in L(P_{i \equiv 2 \pmod{4}}) \text{ for } k = m - \frac{i}{2},\]

3. \[s_j + w \in L(P_{i \equiv 1 \pmod{4}}) \text{ for } j = \frac{i-1}{2},\]

4. \[s_j + w \in L(P_{i \equiv 0 \pmod{4}}) \text{ for } j = m - \frac{i}{2}.\]

From this observation we can conclude that for \(n_1 < n_2\) we have that \(s_j + w, j \in K\) or \(t_k + w, k \in J\) with \(w \in L_2\) is the vertex label of exactly one component of \(\Gamma(m)\).

Thus, in any case we may conclude that the vertex label \(s_j + w\) or \(t_k + w\) is exactly the label of one vertex in distinct components of \(\Gamma(m)\).

Theorem 2.3. Let T be a tree on m=2l vertices for some positive integer l which is constructed as in Theorem 2.2, where for every \(T_{i,j_i}\) with \(i=2s+1, 0 \le s \le l-1\), the value of \(j_i\) is chosen from \(\{0,2,\ldots,i-1\}\). Then \(T*\Gamma(m)\) is graceful.

Proof. Let f be a graceful labeling of T. Define a new function \(f^*\) for T as follows:

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is odd} \end{cases}\](4)

if \(n_1 \geq n_2\), and

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is odd} \end{cases}\] (5)

if \(n_1 < n_2\).

Note that since the relevant index value of \(j_i\) for \(T_{i,j_i}\) is chosen from \(\{0, 2, ..., i-1\}\), by Eq. (3), if for edge uv in T we have that |f(u) - f(v)| is odd, then the minimum value of \(\{f(u), f(v)\}\) is even. This information is important when determining the value of function \(f^*\) as in Eq.(4) and Eq.(5).

Then the proof will be divided into two cases:

• (i) \(n_1 > n_2\), and
• (ii) \(n_1 < n_2\).

Case (i) By Eq. (4) we have that the new vertex labels of T are \((\frac{n_1+n_2}{2})i+w, i \in \{1,3,\ldots,m-1\}\) and \((\frac{n_1+n_2}{2})i+r+w, i \in \{0,2,\ldots,m-2\}\). Then the label of the edge uv in T if |f(u)-f(v)| odd (say f(u) < f(v)) will be

\[|f^*(u) - f^*(v)| = |f(u)(\frac{n_1 + n_2}{2}) + r + w - f(v)(\frac{n_1 + n_2}{2}) - w|\] \[= |(f(u) - f(v))(\frac{n_1 + n_2}{2}) + r|\] \[= (f(v) - f(u))(\frac{n_1 + n_2}{2}) - r,\]

and if |f(u) - f(v)| even will eventually be

\[|f^*(u) - f^*(v)| = |f(u)(\frac{n_1 + n_2}{2}) - f(v)(\frac{n_1 + n_2}{2})|\]\[= |f(u) - f(v)|(\frac{n_1 + n_2}{2}).\]

Case (ii) Based on Eq. (5), the produced new vertex labels of T are \((\frac{n_1+n_2}{2})i+w, i \in \{0,2,\ldots,m-1\}\)2} and \((\frac{n_1+n_2}{2})i+r+w\), \(i \in \{1,3,\ldots,m-1\}\). Thus, the label of the edge uv of T if |f(u)-f(v)|odd (say f(u) < f(v)), will be

\[\begin{split} |f^*(u) - f^*(v)| &= |f(u)(\frac{n_1 + n_2}{2}) + w - f(v)(\frac{n_1 + n_2}{2}) - r - w| \\ &= |(f(u) - f(v))(\frac{n_1 + n_2}{2}) - r| \\ &= (f(v) - f(u))(\frac{n_1 + n_2}{2}) + r, \\ \text{and if } |f(u) - f(v)| \text{ even will finally be} \\ |f^*(u) - f^*(v)| &= |f(u)(\frac{n_1 + n_2}{2}) - f(v)(\frac{n_1 + n_2}{2})| \\ &= |f(u) - f(v)|(\frac{n_1 + n_2}{2}). \end{split}\]

Then the edge labels of \[T\] are: \[\{ \frac{(n_1+n_2)}{2} 2, \frac{(n_1+n_2)}{2} 4, \dots, \frac{(n_1+n_2)}{2} (m-2) \} \bigcup \{ \frac{(n_1+n_2)}{2} - r, \frac{(n_1+n_2)}{2} 3 - r, \dots, \frac{(n_1+n_2)}{2} (m-1) - r \} = \{ N(m) - N(m-1), N(m) - N(m-2), \dots, N(m) - N(1) \}, \text{ if } n_1 \geq n_2, \text{ or } \{ \frac{(n_1+n_2)}{2} 2, \frac{(n_1+n_2)}{2} 4, \dots, \frac{(n_1+n_2)}{2} (m-2) \} \bigcup \{ \frac{(n_1+n_2)}{2} + r, \frac{(n_1+n_2)}{2} 3 + r, \dots, \frac{(n_1+n_2)}{2} (m-1) + r \} = \{ N(m) - N(m-1), N(m) - N(m-2), \dots, N(m) - N(1) \}, \text{ if } n_1 < n_2.\]

These labels will complete m-1 missing edge labels of \(\Gamma(m)\) as in Lemma 2.1. Then by Lemma 2.3, we conclude that \(T^*\Gamma(m)\) is graceful.

Example 4. Let T be a graceful tree on six vertices and \(\Gamma(6)\) be a collection of suplementary-pairs as in Figure 7. The graph of the resulting graceful tree \(T * \Gamma(6)\) is shown in Figure 8.

In the following we will introduce a similar technique with core tree T of m = 2l + 1 vertices, for some positive integer l. The proof of the following lemma is similar to the proof of Lemma 2.3.

Let \(\Gamma(m)\), m=2l+1 for some positive integer l, be a collection of interlaced trees and \(\{T_i, T_{i+1}\}\\) be a supplementary-pair for every \(i \in \{2, 4, \dots, m-1\}\), with \(n_i = n_2\) and \(n_{i+1} = n_3\), and \(T_1\) be with \(n_1 = n_2 + n_3\) vertices, \(p_1 = p_1^*\), such that the following properties hold.

(a') If \[n_2 \ge n_3\] then \(p_{i\equiv 2 \pmod{4}}, p^*_{i\equiv 1 \pmod{4}} > r\) and

(b') If \[n_2 < n_3\] then \(p_{i \equiv 0 \pmod{4}}, p_{i \equiv 3 \pmod{4}}^* > r\),

with \[n_i = n_2\], \(n_{i+1} = n_3\) and \(r = \lfloor \frac{n_2 - n_3}{2} \rfloor\).

Let \[J'=\{1,3,...,m-2\}, K'=\{0,2,...,m-1\}, L'_1=\{0,1,...,min\{p_{i\equiv 1(\bmod{4})}-r-1,p^*_{i\equiv 2(\bmod{4})}-r-1,p^*_{i\equiv 2(\bmod{4})}-1,p^*_{i\equiv 0(\bmod{4})}-1\}\}\] and \(L'_2=\{0,1,...,min\{p_{i\equiv 1(\bmod{4})}-1,p^*_{i\equiv 2(\bmod{4})}-1,p^*_{i\equiv 2(\bmod{4})}-1,p^*_{i\equiv 0(\bmod{4})}-r-1\}\}\). We denote by \(s_j=(\frac{n_2+n_3}{2})j\) and \(t_k=(\frac{n_2+n_3}{2})k+r\).

Figure 7. A collection of supplementary-pair trees Γ(6) and its core tree T.

Figure 8. The resulting T ∗ Γ(6) with r = 1 and w = 0.

Lemma 2.4. Let \(\Gamma(m)\), m=2l+1 for some positive integer l, be a collection of m interlaced trees and \(\{T_i,T_{i+1}\}\) for \(i=\{2,4,\ldots,m-1\}\) be a supplementary-pair with \(n_i=n_2,n_{i+1}=n_3\) and \(T_1\) be a tree with \(n_1=n_2+n_3\) vertices and \(p_1=p_1^*\) satisfying the properties (a') and (b') above. Then, we can label \(\Gamma(m)\) such that there exists exactly one vertex in each component of \(\Gamma(m)\) having label \(s_j+w\) or \(t_k+w\), with \(j\in K'\), \(k\in J'\), and \(w\in L'_1\) if \(n_2\geq n_3\), or with \(j\in J'\), \(k\in K'\) and \(w\in L'_2\) if \(n_2< n_3\).

Proof. The proof for \(\Gamma(m)-T_1\) is the same as in Lemma 2.3 by considering \(T_2\) as \(T_1\) of Lemma 2.3. From this we can conclude that there exists exactly one vertex in each component of \(\Gamma(m)\) having label \(s_j+w\) or \(t_k+w\), with \(j\in\{1,3,\ldots,m-2\}\), \(k\in\{0,2,\ldots,m-1\}\), and \(w\in L_1'\) if \(n_2\geq n_3\) or with \(j\in\{0,2,\ldots,m-1\}\), \(k\in\{1,3,\ldots,m-2\}\) and \(w\in L_2'\) if \(n_2< n_3\). Now we add \(\frac{n_2+n_3}{2}\) to each vertex label of \(\Gamma(m)-T_1\). We notice that the property on the existence of one vertex with label \(s_j+w\) or \(t_k+w\) in \(\Gamma(m)-T_1\) is still maintained. More precisely we have that every component of \(\Gamma(m)-T_1\) has exactly one vertex with label \(s_j+w\) or \(t_k+w\) with \(j\in K'-\{0\}\), \(k\in J', w\in L_1'\) if \(n_2\geq n_3\) or with \(j\in J', k\in K'-\{0\}, w\in L_2'\) if \(n_2< n_3\). Now we label \(T_1\) by using label function as in Eq. (1) with \(P=P_1\). This implies that \(L(P_1)=\{0,1,\ldots,\frac{n_2+n_3}{2}-1\}\) and \(L(P_1^c)=\{N(m)-\frac{n_2+n_3}{2},N(m)-\frac{n_2+n_3}{2}+1,\ldots,N(m)-1\}\). Since \(s_0+w=w\) and \(t_0+w=r+w\) and the range of w, we have \(min(L(P_1))=0\leq s_0+w\leq s_0+w\)

Theorem 2.4. Let T be a tree on m=2l+1 vertices for some positive integer l which is constructed as in Theorem 2.2, where for every \(T_{i,j_i}\) with \(i=2s+1, 0 \le s \le l\), the value of \(j_i\) is chosen from \(\{1,3,\ldots,i-2\}\). Then \(T*\Gamma(m)\) is graceful.

\(t_0+w<\frac{n_2+n_3}{2}-1=max(L(P_1)).\) So, we can conclude that \(s_0+w,t_0+w\in L(P_1).\) It implies

Proof. Let f be a graceful labeling of T. Define a new function \(f^*\) for T as follows:

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is odd} \end{cases}\] (6)

if \(n_1 \geq n_2\), and

that \(s_0 + w, t_0 + w \in L(V(T_1))\).

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is odd} \end{cases}\] (7)

if \(n_1 < n_2\).

The algebraic process is skipped because it is the same as in Theorem 2.3. We conclude that the new vertex labels of T are either:

\((\frac{n_1+n_2}{2})i+w, i\in\{0,2,\dots,m-1\}\) and \((\frac{n_1+n_2}{2})i+r+w, i\in\{1,3,\dots,m-2\}\) if \(n_1\geq n_2\),, or \((\frac{n_1+n_2}{2})i+w, i\in\{1,3,\dots,m-2\}\) and \((\frac{n_1+n_2}{2})i+r+w, i\in\{0,2,\dots,m-1\}\) if \(n_1< n_2\). Then we get the edge labels of T are either:

\[\{ \frac{(n_1+n_2)}{2} 2, \frac{(n_1+n_2)}{2} 4, \dots, \frac{(n_1+n_2)}{2} (m-1) \} \bigcup \{ \frac{(n_1+n_2)}{2} - r, \frac{(n_1+n_2)}{2} 3 - r, \dots, \frac{(n_1+n_2)}{2} (m-2) - r \} = \{ N(m) - N(m-1), N(m) - N(m-2), \dots, N(m) - N(1) \}, \text{ if } n_1 \ge n_2, \text{, or }\]

Example 5. Let \(\Gamma(7)\) be the collection of suplementary-pair trees in Figure 7 with \(T_1\) as in Figure 9, and \(T_{i+1} := T_i, i = 1, 2, \dots, 6\). Furthermore, the core tree T be a tree with seven vertices as in Figure 9. The resulting graceful tree \(T * \Gamma(7)\) is shown in Figure 10.

Figure 9. \(T_1\) and a core tree T.

Figure 10. \(T * \Gamma(7)\).

Let \(\Gamma(m)\), m=2l+1 for some positive integer l, be a collection of interlaced trees and \(\{T_i, T_{i+1}\}\) be a supplementary-pair for every \(i \in \{2, 4, \ldots, m-1\}\), with \(n_i = n_2\) and \(n_{i+1} = n_3\), and \(T_1\) is with \(n_1 = n_2 + n_3\) vertices, \(p_1 = p_1^*\), such that the following properties hold.

(a") If \[n_2 \ge n_3\] then \(p_{i\equiv 0 \pmod 4}, p^*_{i\equiv 3 \pmod 4} > r\) and

(b") If \[n_2 < n_3\] then \(p_{i \equiv 2 \pmod{4}}, p^*_{i \equiv 1 \pmod{4}} > r\), with \(n_i = n_2, n_{i+1} = n_3\) and \(r = \lfloor \frac{n_2 - n_3}{2} \rfloor\).

Lemma 2.5. Let \(\Gamma(m)\), m=2l+1 for some positive integer l, be a collection of interlaced trees and \(\{T_i, T_{i+1}\}\) for \(i=\{2,4,\ldots,m-1\}\) be a supplementary-pair with \(n_i=n_2, n_{i+1}=n_3\) and \(T_1\) be a tree with \(n_1=n_2+n_3\) vertices and \(p_1=p_1^*\) satisfying the properties (a'') and (b'') above. Then, we can label \(\Gamma(m)\) such that there exists exactly one vertex in each component of \(\Gamma(m)\) which has label \(s_j+w\) or \(t_k+w\) with \(j\in J'\), \(k\in K'\), and \(w\in L'_2\) if \(n_2\geq n_3\) or with \(j\in K'\), \(k\in J'\) and \(w\in L'_1\) if \(n_2< n_3\).

Proof. The proof is the same as in Lemma 2.4, so the detail is skiped here for the sake of space efficiency. \(\Box\)

Theorem 2.5. Let T be a tree on m=2l+1 vertices for some positive integer l which is constructed as in Theorem 2.2, where for every \(T_{i,j_i}\) with \(i=2s+1, 0 \le s \le l\), the value of \(j_i\) is chosen from \(\{0, 2, ..., i-1\}\). Then \(T * \Gamma(m)\) is graceful.

Proof. Let f be a graceful labeling of T. Define a new function \(f^*\) for T as follows:

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is odd} \end{cases}\] (8)

if \(n_1 \geq n_2\), and

\[f^*(v) = \begin{cases} f(v)(\frac{n_1 + n_2}{2}) + w, & \text{if } f(v) \text{ is even} \\ f(v)(\frac{n_1 + n_2}{2}) + r + w, & \text{if } f(v) \text{ is odd} \end{cases}\](9)

if \(n_1 < n_2\).

We skip the detail of calculation process which is the same as in the proof of Theorem 2.3. Then, we may conclude that the new vertex labels of T are either:

\[(\frac{n_1+n_2}{2})i+w, \ i\in \{1,3,\dots,m-2\} \ \text{and} \ (\frac{n_1+n_2}{2})i+r+w, \ i\in \{0,2,\dots,m-1\} \ \text{if} \ n_1\geq n_2, \\ \text{or} \ (\frac{n_1+n_2}{2})i+w, \ i\in \{0,2,\dots,m-1\} \ \text{and} \ (\frac{n_1+n_2}{2})i+r+w, \ i\in \{1,3,\dots,m-2\} \ \text{if} \ n_1< n_2.\]

From this we can immediately see that the edge labels of T are either

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

These labels will complete m-1 missing edge labels of \(\Gamma(m)\) as in Lemma 2.1. Thus by Lemma 2.5, we conclude that \(T^*\Gamma(m)\) is graceful.

Acknowledgement

We express our gratitude to anonymous referees for their support and suggestions for the refinement of this article performance.

References

• [1] U.N. Deshmukh, Applications of graceful graphs, International Journal of Engineering Sciences and Research Technology 4 (2015), 129–131.
• [2] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2019), DS6.
• [3] K.M. Koh, D.G. Rogers and T. Tan, Two theorems on graceful trees, Discrete Math. 25 (1979), 141–148.
• [4] K.M. Koh, D.G. Rogers and T. Tan, Interlaced trees: a class of graceful trees, in: Combinatorial mathematics VI: Proc. Sixth Australian Conference, Armidale, Lecture Notes in Math. (Springer-Verlag, Berlin, 1979).
• [5] K.M. Koh, D.G. Rogers and T. Tan, Products of graceful trees, Discrete Math. 31 (1980), 279–292.
• [6] K.M. Koh, D.G. Rogers and T. Tan, Another class of graceful trees, J. Aust. Math. Soc. (Series A) 31 (1981), 226–235.
• [7] D. Mishra, S.K. Rout, and P.C. Nayak, Some new graceful generalized Classes of diameter six trees, Electron. J. Graph Theory Appl. 5 (2017), 94–111.
• [8] R.G. Stanton and C.R. Zarnke, Labeling of balanced trees, in: Proc. Fourth South Eastern Conference, Boca Raton, Congr. Numer. 8 (Utilitas Math., Winnipeg, 1973).