Let \(G=(V(G),E(G))\) be a simple, finite and undirected graph of order \(p\) and size \(q\). For \(k\ge 1\), a bijection \(f: V(G)\cup E(G) \to \{k, k+1, k+2, \ldots, k+p+q-1\}\) such that \(f(uv)= |f(u) – f(v)|\) for every edge \(uv\in E(G)\) is said to be a \(k\)-super graceful labeling of \(G\). We say \(G\) is \(k\)-super graceful if it admits a \(k\)-super graceful labeling. In this paper, we study the \(k\)-super gracefulness of some complete multi-partite graphs.
Let \(G=(V(G),E(G))\) (or \(G=(V,E)\) for short) be a simple, finite and undirected graph without isolated vertex of order \(|V|=p\) and size \(|E| = q\) \((q\ge 1)\). \(G\) is also called a \((p,q)\)-graph. For integers \(a\) and \(b\) with \(a\le b\), let \(\mathbf{[a,b]}\) be the set of integers between \(a\) and \(b\) inclusively. All notation not defined in this paper can be found in [3]. Rosa [12] defined a graceful labeling of \(G\) as an injective vertex labeling function \(f: V\to \mathbf{[0,q]}\) such that the induced edge-labeling function \(f^*(uv)=|f(u)-f(v)|\) for every \(uv\in E\) is also injective. The following conjecture has since then become one of the most famous unsolved graph labeling problems.
Conjecture 1.1. All trees are graceful.
Since then, there have been more than 1500 research papers on graph labelings (see the dynamic survey by Gallian [5]). Interested readers may refer to [2, 4] for two variations on graceful labelings.
In [1], Bange et al. defined a \(k\)-sequentially additive labeling \(f\) of a graph \(G\) as a bijection from \(V\cup E\) to \(\mathbf{[k,k+p+q-1]}\) such that for each edge \(uv\in E\), \(f(uv)=f(u)+f(v)\). A graph \(G\) admitting a \(k\)-sequentially additive labeling is called a \(k\)-sequentially additive graph. If \(k=1\), then \(G\) is called a simply sequentially additive graph or an SSA-graph. They conjectured that all trees are SSA-graphs. More results on \(k\)-sequentially additive labeling can be found in [6, 7, 9].
In [8], the concept of \(k\)-super graceful labeling was introduced. This was referred to as a \(k\)-sequential labeling in [13] that we are only awared after the completion of this paper.
Definition 1.2. Given \(k\ge 1\), a bijection \(f: V\cup E \to \mathbf{[k, k+p+q-1]}\) is called a \(k\)-super graceful labeling if \(f(uv) = |f(u)-f(v)|\) for every edge \(uv\) in \(G\). We say \(G\) is \(k\)-super graceful if it admits a \(k\)-super graceful labeling.
This is a generalization of a super graceful labeling defined in [10, 11]. For simplicity, 1-super graceful is also known as super graceful. Properties of \(k\)-super gracefulness and sufficient conditions on the existence of \(k\)-super graceful labeling of various bipartite and tripartite graphs with arbitrarily large maximum vertex degree have been investigated [8]. Motivated by this, in this paper, we study the \(k\)-super gracefulness of some complete multi-partite graphs.
Let \(G+H\) be the disjoint union of graphs \(G\) and \(H\). Let \(nG\) be the disjoint union of \(n\ge2\) copies of \(G\). Suppose a graph \(G\) admits a \(k\)-super graceful labeling with the edge-label set \(A\). We will say that \(G\) is \(k\)-super graceful with edge-label set \(A\) or with edges in the set \(A\). The following 2 results were obtained in [8].
Theorem 2.1. For \(k\ge 1\), if a \((p,q)\)-graph \(G\) admits a \(k\)-super graceful labeling, then the \(k\) largest integers in \(\mathbf{[k,k+p+q-1]}\) must be vertex labels of \(k\) mutually non-adjacent vertices. Moreover, no two of the \(k+1\) smallest integers are vertex labels of adjacent vertices.
Corollary 2.2. If \(G\) is \(k\)-super graceful, then \(1\le k\le\alpha\), where \(\alpha\) is the independence number of \(G\). Moreover, the upper bound is sharp.
Lemma 2.3. If \(G\) is \(k\)-super graceful with all vertices labeled by odd integers or all vertices labeled by even integers, then \(k=1\).
Theorem 2.4. If \(G\) is \(k\)-super graceful with all vertices labeled by odd integers, then \(G\) is a \((q+1,q)\)-graph and \(k=1\), where \(q\ge 1\).
The following conjecture is equivalent to the Graceful Tree Conjecture.
Conjecture 2.5. Each tree admits a super graceful labeling with all odd vertex labels.
Theorem 2.6. A graph \(G\) is \(k\)-super graceful with all odd edge labels if and only if \(k=1\) and \(G\) is a star \(K(1,q)\), \(q\ge 1\).
In this section, we shall focus on complete \(t\)-partite graphs for \(t\ge 2\). First, we study the \(k\)-super gracefulness of the complete bipartite graph \(K(m,n)\). It was shown in [10, 8] the complete bipartite graph \(K(m,n)\) is \(1\)-, \(m\)– and \(n\)-super graceful for all \(n\ge m\ge 2\) whereas \(K(1,q)\) is \(k\)-super graceful if and only if \(q\equiv 0\pmod{k}\).
Theorem 3.1. Suppose \(K(m,n)\) with the bipartition \((A,B)\) admits a \(k\)-super graceful labeling \(f\), where \(n=|B|\ge m=|A|\ge 2\). Suppose \(f\) assigns even integers to \(a\) vertices in \(A\) and \(b\) vertices in \(B\), respectively.
(i) If \(m,n\) are even, then \(a=m/2, b=n/2\) or \(a=(m-2)/2, b=(n-2)/2\).
(ii) If \(m,n\) are odd, then \(k\) is odd with \(a=(m-1)/2\), \(b=(n-1)/2\).
(iii) If \(m,n\) are of different parity, then \(k\) is odd implies that \(m\) is odd with \(a=(m-1)/2\) or \(n\) is odd with \(b=(n-1)/2\); and \(k\) is even implies \(a=(m-2)/2, b=(n-3)/2\); or \(a=(m-3)/2, b=(n-2)/2\); or \(a=m/2, b=(n+1)/2\); or \(a=(m+1)/2, b=n/2\).
Proof. Note that, the total number of even labels under \(f\) is \(a+b+ab + (m-a)(n-b)\), and the total number of odd labels under \(f\) is \((m-a) + (n-b) + b(m-a) + a(n-b)\).
Suppose \(m,n\) are even. We then have equal numbers of odd and even labels. Hence, \((m-a) + (n-b) + b(m-a) + a(n-b) = a+b+ab + (m-a)(n-b)\) which implies that \((m-2a-1)(n-2b-1)=1\) so that \(a=m/2, b=n/2\) or \(a=(m-2)/2, b=(n-2)/2\).
Suppose \(m\) or \(n\) is odd. We then consider 2 cases:
Case 1. \(k\) is odd. In this case, the number of even labels is one less than the number of odd labels. Hence, \(a+b+ab + (m-a)(n-b) + 1 = (m-a) + (n-b) + b(m-a) + a(n-b)\) which implies that \((m-2a-1)(n-2b-1)=0\) so that \(a=(m-1)/2\) or \(b=(n-1)/2\). Hence \(m\equiv n\equiv 1\pmod 2\).
Case 2. \(k\) is even. In this case, the number of odd labels is one less than the number of even labels. Hence, \(a+b+ab + (m-a)(n-b) = (m-a) + (n-b) + b(m-a) + a(n-b) + 1\) which implies that \((m-2a-1)(n-2b-1)=2\) so that \(a=(m-2)/2, b=(n-3)/2\) or \(a=(m-3)/2, b=(n-2)/2\) or \(a=m/2, b=(n+1)/2\) or \(a=(m+1)/2, b=n/2\). \(\square\)
By Theorem 3.1, we conclude that \(K(3,3)\) is not 2-super graceful, \(K(2,4)\) is not 3-super graceful and \(K(3,5)\) is neither 2- nor 4-super graceful. Suppose \(K(3,4)\) has a 2-super graceful labeling \(f\). By Theorem 3.1 (iii), we have \(a=0, b=1\) or \(a=b=2\). Suppose \(a=0, b=1\). By Theorem 2.1, 20 and 19 are labels of vertices of \(B\). Hence, 18 cannot be a label, a contradiction. Suppose \(a=b=2\). Let \(A=\{x,y,z\}\) and \(B=\{s,t,u,v\}\). Suppose \(f(x), f(y), f(s), f(t)\) are even and \(f(x)>f(y)\), \(f(s)>f(t)\) and \(f(u)>f(v)\). By Theorem 2.1, we consider two cases.
(a) \(f(x)=20,f(z)=19\) so that \(f(xt)=18\) or \(f(y) = 18\).
(1) \(f(xt)=18\). We have \(f(t)=2\) and \(f(zt)=17\). This implies that \(f(yt)\ne 16\) and \(3\not\in\{f(u), f(v), f(xu), f(xv)\}\). This forces \(f(yu)=3\), \(f(yv)=3\) or \(f(zs)=3\).
(1.1) \(f(yu)=3\) or \(f(yv)=3\) implies that \(16\not\in\{f(zu), f(zv)\}\). Hence \(f(xs)=16\), \(f(ys)=16\) or \(f(y)=16\).
When \(f(ys)=16\), then either \(f(y)\) or \(f(s)\) is greater than 16 which is impossible.
When \(f(xs)=16\), we have \(f(s)=4\) and \(f(zs)=15\). Hence \(f(y)\le 14\). Since \(f(x)=20\), \(f(zu)<f(zv)\le 13\), \(f(u)\ge 9\) and \(f(v)\ge 7\). Then \(f(zu)\le 10\) and \(f(zv)\le 12\). Thus \(f(y)=14\). Then \(f(ys)=10\) and \(f(yt)=12\). Hence \(f(zv)=6\). This forces \(f(v)=13\) and \(f(yv)=1\) which is a contradiction.
When \(f(y)=16\). Then \(f(yt)=14\). Since \(f(yu)=3\) or \(f(yv)=3\) and \(15>f(u)>f(v)\), \(f(u)=13\). Thus \(f(zu)=6\) and \(f(xu)=7\). Since \(10\notin \{f(s), f(ys), f(xs)\}\), \(f(zv)=10\) and hence \(f(v)=9\). So that \(f(yv)=7\) which is impossible.
(1.2) \(f(zs)=3\) implies \(f(s)=16\) and hence \(f(xs)=4\). It forces that \(f(y)\notin\{6,8,12,14\}\), i.e., \(f(y)=10\). Hence \(f(ys)=6\) and \(f(yt)=8\). Then \(f(zv)=14\) and \(f(v)=5\). Since \(f(y)=10\), \(f(yv)=5\) which is impossible.
(2) \(f(y) = 18\). Since \(3\le f(yu)<f(yv)\), \(15\ge f(u)>f(v)\). This implies \(f(zu)\ge 4\). Since \(f(xt)>f(xs)>f(ys)\) and \(f(xt)>f(yt)>f(ys)\), \(f(ys)=2\). So that \(f(s)=16\), \(f(xs)=4\) and \(f(zs)=3\). Now, there is no way to assign 17.
(b) \(f(s)=20,f(u)=19\) so that \(f(ys)=18\) or \(f(t)=18\).
(1) \(f(ys)=18\). We have \(f(y)=2\) and \(f(yu)=17\). This forces \(f(t)=16\) or \(f(xs)=16\).
(1.1) \(f(t)=16\) implies \(f(xt)=14\). Then there is no way to label \(x\).
(1.2) \(f(xs)=16\) implies \(f(x)=4\) and \(f(xu)=15\). Since \(15\) and \(17\) are assigned, \(f(z)\ge 7\) and \(f(v)\le 13\). This implies \(f(zu), f(zv)\le 12\). This forces \(f(t)=14\). Hence \(f(yt)=12\) and \(f(xt)=10\). It is easy to check that \(f(zu)\) is neither 6 nor 8. So \(f\) does not exist.
(2) \(f(t)=18\). Then \(f(z)\le 15\), \(f(zt)\le 15\) and \(16\ge f(x)>f(y)\ge 4\). So \(f(ux)<f(uy)\le 15\). Since \(f(y)<f(x)\le 16\), \(f(xv)\le 13\) and \(f(yv)\le 11\). Thus \(f(zs)=17\) or \(f(v)=17\).
(2.1) \(f(zs)=17\) implies \(f(z)=3\), \(f(zu)=16\) and \(f(zt)=15\). Now \(f(zv)\le 10\). Thus \(f(x)=14\) or \(f(ys)=14\).
When \(f(x)=14\), then \(f(y)\le 12\). There is no room to assign the label 13.
When \(f(xs)=14\), then \(f(x)=6\) and hence \(f(y)\le 4\). Then \(f(yt)=14\) or \(16\). It is impossible.
(2.2) \(f(v)=17\). Then \(f(z)\ge 5\) and hence \(f(zv)\le 12\). Note that \(f(xt)<f(xs)<f(ys)\), \(f(xt)<f(yt)<f(ys)\). Thus \(f(ys)=16\). So that \(f(y)=4\), \(f(yt)=14\), \(f(yu)=15\), \(f(yv)=13\). Now \((f(xv), f(xt), f(xu), f(xs))\) and \((f(zv), f(zt), f(zu), f(zs))\) are two disjoint increasing sequence of four consecutive undetermined labels. The first one starts with an odd label and the last one starts with an even label. But they do not exist.
Hence, for \((m,n)= (2,2)\), \((2,3)\), \((2,4)\), \((3,3)\), \((3,4)\), \((3,5)\), \(K(m,n)\) is \(k\)-super graceful if and only if \(k=1,m,n\).
Lemma 3.2. Suppose \(n\ge 2\), the graph \(K(2,n)\) is \(k\)-super graceful if and only if \(k=1,2,n\).
Proof. Let the two partite sets of \(K(2,n)\) be \(A = \{u_1, \ldots, u_n\}\) and \(B = \{v_1, v_2\}\). The sufficiency follows from [10, Theorem 2.5] and [8, Theorem 4.5]. To prove the necessity, we just need to show that if \(K(2, n)\) is \(k\)-super graceful, with \(k \ge 3\) and \(n\ge 3\), then \(k = n\).
Let \(f\) be a \(k\)-super graceful labeling of \(K(2,n)\). The available label set is \(\mathbf{[k, k + 3n + 1]}\). We may assume \(f(u_1)>f(u_2)>\cdots >f(u_n)\) and \(f(v_1)<f(v_2)\). Let \(j\) be the greatest so that the \(j\) integers \(k + 3n + 1, k + 3n, \ldots, k + 3n + 2 – j\) are labels of mutually non-adjacent vertices. By Theorem 2.1, we have \(n \ge j \ge k \ge 3\). Thus these vertices are in \(A\). Hence \(f(u_i) = k + 3n + 2 – i\), for \(i = 1, \ldots, j\). Consider the largest undetermined label, \(k + 3n + 1 – j\). It cannot label a vertex in \(A\), by the maximality of \(j\). If it labels a vertex in \(B\), then the edge joining it to \(u_j\) has label \(1 < k\), which is impossible. Thus it must be the largest edge label. So we must have \(f(u_1v_1) = k + 3n + 1 – j\), \(f(v_1)=j\). Thus \(f(u_iv_1) = k + 3n + 2 – i – j\), for \(i = 1, \ldots, j\). Consider the label \(k + 3n + 1 – 2j\). Since it is the largest undetermined label, it must be the label of \(u_1v_2\), \(v_2\) or \(u_{j+1}\) if it exists.
Suppose \(f(u_1v_2) = k + 3n + 1 – 2j\). We have \(f(v_2)= 2j\). Consequently, labels of \(u_2v_2\) to \(u_jv_2\) are \(k+3n-2j\) to \(k+3n+2-3j\). If \(u_{j+1}\) exists, then we must label \(u_{j+1}\) to \(u_{2j}\) by \(k+3n+1-3j\) to \(k+3n+2-4j\) so that the labels of \(u_{j+1}v_2\) to \(u_{2j}v_2\) are \(k+3n+1-5j\) to \(k+3n+2-6j\). This argument can be repeated until all vertices in \(A\) are labeled. Hence \(n\equiv 0\pmod{j}\). We see that there is a gap of integers from \(j+1\) to \(2j-1\) and all other used labels, except \(j\) and \(2j\), are consecutive. This labeling is not \(k\)-super graceful, a contradiction. Thus \(k+3n+1-2j\) must be a vertex label.
Suppose \(f(u_{j+1})=k+3n+1-2j\) if \(j<n\). Now we consider the largest undetermined label \(k+3n-2j\). Since \(f(u_{j+1}v_2)\ge k>2\), \(f(v_2)\le k+3n-2j-2\). If \(k+3n-2j=f(u_iv_2)\) for some \(i\), then \(i=1\) and hence \(f(v_2)=2j+1\). But \(f(u_jv_2)=k+3n+1-3j=f(u_{j+1}v_1)\). This is a contradiction. So \(k+3n-2j\) must be a vertex label and hence \(f(u_{j+2})=k+3n-2j\). By a similar argument we can show that \(k + 3n+1 – 2j, \ldots, k + 3n + 2 – 3j\) are labels of \(u_{j+1}, \dots u_{2j}\) and \(k + 3n +1- 3j, \ldots, k + 3n + 2 – 4j\) are labels of \(u_{j+1}v_1, \dots u_{2j}v_1\), respectively. This argument can be repeated until all vertices in \(A\) are labeled. Hence \(n=rj\) for some \(r\ge 2\). In this case, integers in \(\mathbf{[k+rj+2, k+3rj+1]}\) are assigned to \(A\cup E_1\). Now integers in \(\mathbf{[k, k+rj+1]}\setminus \{j, f(v_2)\}\) must be assigned to \(E_2\). But labels assigned to \(E_2\) form \(r\) subintervals with \(r-1\) gaps of length \(j\ge 3\). So it is impossible.
Suppose \(f(v_2) = k + 3n + 1 – 2j\). Then the edges joining \(v_2\) to the first \(j\) vertices in \(A\) have labels \(2j, \ldots, j + 1\). Now consider the next label \(k + 3n – 2j > j = f(v_1)\). Since it is the largest undetermined label, it must be the label of \(f(u_{j+1})\) or \(f(u_{j+1}v_2)\) if \(u_{j+1}\) exists. In either case, \(1\) is a label, a contradiction. Thus, \(u_{j+1}\) does not exist and hence \(j=n\). Now \(\mathbf{[n, 2n+1]}\cup \mathbf{[k+n+2, k+3n+1]}=\mathbf{[k, k+3n+1]}\). Hence \(n=k\). \(\square\)
Lemma 3.3. Let \(m, n, k \ge 2\). If \(K(m, n)\) is \(k\)-super graceful, and the \(n\) greatest integers in \(\mathbf{[k, k + m + n + mn – 1]}\) are labels of the partite set with \(n\) vertices, then \(k = n\).
Proof. Let the two partite sets of \(K(m, n)\) be \(A = \{u_1, \ldots, u_n\}\) and \(B = \{v_1, \ldots, v_m\}\). Without loss of generality, assume that \(f(v_1) < f(v_2) < \cdots < f(v_m)\), where \(f\) denotes the labeling. Furthermore, let \(E_i\) be the set of edges joining \(v_i\) to the vertices in \(A\), for \(i = 1, \ldots, m\).
By Theorem 2.1, \(n \ge k \ge 2\). We may assume that \(f(u_j) = k + m + n + mn – j\), for \(j = 1, \ldots, n\). Consider the greatest undetermined label, \(k + m + mn – 1\). If it labels a vertex in \(B\), then the edge joining it to \(u_n\) has label \(1 < k\), which is impossible. Thus it must be the greatest edge label. This gives \(f(u_1v_1) = k + m + mn – 1\), \(f(v_1) = n\), and \(f(u_jv_1) = k + m + mn – j\), for \(j = 1, \ldots, n\).
The labels of the vertices in \(A\) form a block of \(n\) consecutive integers consisting of the greatest \(n\) labels, and the labels of the edges in \(E_1\) form another block of \(n\) consecutive integers consisting of the second greatest \(n\) labels. Similarly, for each \(i = 2, \ldots, m\), the labels of the edges in \(E_i\) form a block of \(n\) consecutive integers. These blocks of consecutive integers cannot overlap, because they consist of labels of distinct edges. By the assumption on the labels of the vertices in \(B\), the edge labels in each succeeding block must be less than the edge labels in each preceding block. They give at most \(m\) gaps, between the labels of the edges in \(E_i\) and the labels of the edges in \(E_{i+1}\), for \(i = 1, \ldots, m – 1\), and the integers in \(\mathbf{[k, k + m + n + mn – 1]}\) that are less than the smallest label of the edges in \(E_m\).
Each pair of \(f(v_i)\) and \(f(v_{i+1})\) cannot represent consecutive integers, because otherwise \(f(u_1v_{i+1}) = k + m + n + mn – 1 – f(v_{i+1}) = k + m + n + mn – 2 – f(v_i) = f(u_2v_i)\), resulting in two edges having the same label.
Since there are \(m\) vertices in \(B\), no two of which with consecutive labels, and there are at most \(m\) gaps, we must have exactly \(m\) gaps of one integer to label the vertices in \(B\). This forces the smallest of these vertex labels, namely \(f(v_1)\), to be \(k\). As we have established that \(f(v_1) = n\), this gives the desired result of \(k = n\). \(\square\)
Conjecture 3.4. For \(m=1\), and a prime \(n\) or for \(n\ge m\ge 2\), \(K(m,n)\) is \(k\)-super graceful if and only if \(k=1,m,n\).
Theorem 3.5. The graph \(G=K(1,\ldots,1,2)\) of order \(r+2\) \((\ge 4)\) is \(k\)-super graceful if and only if \(r=2,k=1\).
Proof. By [8, Theorem 4.8], the sufficiency holds. Since the independence number of \(G\) is \(2\), by Theorem 2.1, \(1\le k \le 2\).
Suppose \(G\) has a 2-super graceful labeling \(f\). Let \(u\) and \(v\) be the vertices with degree \(r\) and \(w_1, \ldots, w_r\) be the vertices with degree \(r+1\). For convenience we may assume \(f(u) > f(v)\) and \(f(w_1)>f(w_2)>\cdots >f(w_r)\). By Theorem 2.1, we have \(f(u)=m\), \(f(v)=m-1\), where \(m\) is the largest possible label. It follows that \(m-2\) must be a label of the edge \(uw_r\). Hence, \(f(w_r)=2\) and \(f(w_rv) = m-3\). Consequently, \(m-4\) must be a label of the edge \(uw_{r-1}\). Hence, \(f(w_{r-1}) = 4\) which implies that \(f(w_{r-1}w_r) = 2 = f(w_r)\), a contradiction.
Suppose \(G\) has a super graceful labeling \(f\) and \(r\ge 3\). Again, we assume that \(f(u) > f(v)\) and \(f(w_1)>f(w_2)>\cdots >f(w_r)\). Note that \(G\cong K_{r+2}-e\), where \(e=uv\). We let \(H\cong K_r\) be the subgraph induced by \(\{w_1, \dots, w_r\}\). The available label set is \(\mathbf{[1,m]}\). Note that \(m=\frac{(r+1)(r+4)}{2}\ge 14\). By Theorem 2.1, we have 2 cases: \(f(u)=m\) and \(f(w_1)=m\).
1. \(f(u)=m\). There are 3 subcases: \(f(v)=m-1\), \(f(uw_r)=m-1\) and \(f(w_1)=m-1\).
1.1: Suppose \(f(v)=m-1\). Since the maximum vertex label in \(H\) is at most \(m-2\), \(m-2=f(w_1)\) or \(m-2=f(uw_r)\).
a) If \(m-2=f(w_1)\), then \(f(uw_1)=2, f(vw_1)=1\). Since \(m-3\) cannot be labeled at vertex or edge in \(H\), \(f(uw_{r})=m-3\). So \(f(w_r)=3\), \(f(vw_r)=m-4\) and \(f(w_1w_r)=m-5\). Thus 4, 5 and 6 are not labeled at vertex of \(H\). Hence \(m-6\ge f(w_2)\) and \(f(w_{r-1})\ge 7\). Thus \(m-6=f(w_2)\). Then \(f(w_1w_2)=4\), \(f(uw_2)=6\) and \(f(vw_2)=5\). Now \(m-7\) cannot be a vertex label or an edge label in \(H\). Hence \(f(uw_{r-1})=m-7\). It forces \(f(w_{r-1})=7\) and \(f(w_{r-1}w_r)=4\) which is a contradiction.
b) If \(m-2=f(uw_r)\), then \(f(w_r)=2\), \(f(vw_r)=m-3\). Now \(f(w_1)\le m-4\). Thus \(f(uw_i)\ge 4\) and \(f(vw_i)\ge 3\). So 1 is an edge label in \(H\). Thus \(H\) must have two vertices say \(y, z\), with \(f(y) = a\) and \(f(z) = a+1\) in \([2, m-4]\) so that \(f(uz) = m-a-1 = f(vy)\), a contradiction.
1.2: Suppose \(f(uw_r)=m-1\). Then \(f(w_r)=1\). Clearly, \(m-2\) must be a vertex label. So either \(f(w_1)=m-2\) or \(f(v)=m-2\).
a) If \(f(w_1)=m-2\), then \(f(uw_1)=2, f(w_1w_r)=m-3\). Thus \(m-4\) cannot be a vertex label. Since \(\max\{f(w_1w_{r-1}), f(w_2w_r)\}\le m-5\), this forces \(f(uw_{r-1})=m-4\). Hence \(f(w_{r-1})=4\), \(f(w_{r-1}w_r)=3\) and \(f(w_1w_{r-1})=m-6\). However, \(m-5\) cannot be placed, a contradiction.
b) If \(f(v)=m-2\), then \(f(vw_r)=m-3\). This forces \(f(uw_{r-1})=m-4\) or \(f(w_1)=m-4\). Assume \(f(uw_{r-1})=m-4\). Then \(f(w_{r-1})=4\), \(f(w_rw_{r-1})=3\), \(f(vw_{r-1})=m-6\). However, \(m-5\) cannot be placed, a contradiction.
Assume \(f(w_1)=m-4\). Then \(f(uw_1)=4\), \(f(vw_1)=2\), \(f(w_1w_r)=m-5\). Note that \(m-5\) is the largest edge label in \(H\) and the next largest edge label is \(\max\{f(w_1w_{r-1}), f(w_2w_r)\}\le m-7\). Since the label \(2\) is fixed, \(m-6\) must be an edge label. Thus, \(m-6\) must be labeled to an edge incident to \(u\) or \(v\). At this moment, \(m-6\) is the largest undetermined label. Since \(f(uw_{r-1})>f(vw_{r-1})\), \(f(uw_{r-1})=m-6\). Hence \(f(w_{r-1})=6\), \(f(vw_{r-1})=m-8\). Since \(f(w_r)=1\), \(f(w_2)\le m-9\) and \(f(w_{r-2})\ge 9\) (this also holds when \(r=3\)). Thus \(m-7\) cannot be placed, a contradiction.
1.3: Suppose \(f(w_1)=m-1\). Then \(f(uw_1)=1\). This forces \(f(uw_r)=m-2\). Hence \(f(w_r)=2\), \(f(w_1w_r)=m-3\). Thus, \(f(w_2)\le m-4\) and \(f(w_{r-1})\ge 4\). So the largest undetermined edge label in \(H\) is at most \(m-5\). Therefore, \(f(v)=m-4\) or \(f(w_2)=m-4\). If \(f(v)=m-4\), then \(f(vw_1)=3\), \(f(vw_r)=m-6\). However, \(m-5\) cannot be placed, a contradiction. If \(f(w_2)=m-4\) so that \(f(uw_2)=4\), \(f(w_1w_2)=3\), \(f(w_2w_r)=m-6\). However, \(m-5\) cannot be placed, a contradiction.
2. \(f(w_1)=m\). There are 4 subcases to consider: (2.1) \(f(u)=m-1\), (2.2) \(f(w_2)=m-1\) (2.3) \(f(vw_1)=m-1\), and (2.4) \(f(w_1w_r)=m-1\).
2.1: Suppose \(f(u)=m-1\). We have \(f(uw_1)=1\). Then \(m-2\) must be labeled to \(w_1w_r\) or \(vw_1\) or \(v\).
a) If \(f(w_1w_r)=m-2\), then \(f(w_r)=2\) and \(f(uw_r)=m-3\). This forces \(m-4\) to be a vertex label. If \(f(w_2)=m-4\), then there is no place to label \(m-5\). If \(f(v)=m-4\), then \(f(vw_1)=4\), \(f(vw_r)=m-6\). However, \(m-5\) cannot be placed, a contradiction.
b) If \(f(vw_1)=m-2\), then \(f(v)=2\). However, \(m-3\) cannot be placed, a contradiction.
c) If \(f(v)=m-2\), then \(f(vw_1)=2\). Then \(m-3\) must the largest edge label in \(H\). So \(f(w_1w_r)=m-3\). Then \(f(w_r)=3\), \(f(uw_r)=m-4\), \(f(vw_r)=m-5\). Now, \(m-6\) must be a vertex label. Hence \(f(w_2)=m-6\). However, \(m-7\) cannot be placed, a contradiction.
2.2: Suppose \(f(w_2)=m-1\). So, \(f(w_1w_2)=1\). This forces \(f(vw_1)=m-2\) or \(f(w_1w_r)=m-2\).
a) If \(f(vw_1)=m-2\), then \(f(v)=2, f(vw_2)=m-3\). Thus \(3\) and \(4\) are not vertex labels in \(H\). Hence the largest edge label in \(H\) is at most \(m-5\).
If \(m-4\) is an edge label, then it must be \(f(uw_1)\). So, \(f(u)=4, f(uw_2)=m-5\). At this moment, \(f(w_r)\ge 7\) and the largest edge label in \(H\) is at most \(m-7\). Thus \(m-6\) must be a vertex label which is \(f(w_3)\). Now, \(m-7\) cannot be placed, a contradiction.
If \(m-4\) is a vertex label, then we have the following two cases:
i) \(f(u)=m-4\). So, \(f(uw_1)=4\), \(f(uw_2)=3\). Now, \(m-5\) cannot be placed, a contradiction.
ii) \(f(w_3)=m-4\). So, \(f(w_2w_3)=3\), \(f(w_1w_3)=4\). Now, \(m-5\) cannot be placed, a contradiction.
b) If \(f(w_1w_r)=m-2\), then \(f(w_r)=2, f(w_2w_r)=m-3\). Thus \(3\) and \(4\) are not vertex labels. Hence the largest undetermined edge label is at most \(m-5\). In other words, \(m-4\) must be a vertex label. So we have the following two cases:
i) \(f(u)=m-4\). Then \(m-5\) cannot be placed, a contradiction.
ii) \(f(w_3)=m-4\). So, \(f(w_1w_3)=4, f(w_2w_3)=3, f(w_3w_r)=m-6\). Now, \(m-5\) cannot be placed, a contradiction.
2.3: Suppose \(f(vw_1)=m-1\) so that \(f(v)=1\). Now, \(m-2\) must be labeled at \(uw_1\) or \(u\) or \(w_2\).
(a) If \(f(uw_1)=m-2\), then \(f(u)=2\). We must have \(f(w_2)=m-3\) so that \(f(w_1w_2)=3\), \(f(vw_2)=m-4\), \(f(uw_2)=m-5\). This forces \(f(w_1w_r)=m-6\). Hence \(f(w_r)=6\), \(f(vw_r)=5\), \(f(uw_r)=4\). However, \(m-7\) cannot be placed, a contradiction.
(b) If \(f(u)=m-2\), then \(m-3\) cannot be placed, a contradiction.
(c) If \(f(w_2)=m-2\), then \(f(w_1w_2)=2, f(vw_2)=m-3\). This forces \(f(w_1w_r)=m-4\) or \(f(uw_1)=m-4\).
i) If \(f(w_1w_r)=m-4\), then \(f(w_r)=4\), \(f(vw_r)=3\), \(f(w_2w_r)=m-6\). However, \(m-5\) cannot be placed, a contradiction.
ii) If \(f(uw_1)=m-4\), then \(m-5\) cannot be placed, a contradiction.
2.4: Suppose \(f(w_1w_r)=m-1\). We have \(f(w_r)=1\). Hence no vertex is labeled by \(2\). This forces \(f(u)=m-2\) or \(f(w_2)=m-2\).
a) If \(f(u)=m-2\), then \(f(uw_1)=2, f(uw_r)=m-3\). Thus, \(m-5\ge f(w_2)\ge f(w_{r-1})\ge 4\). We consider the following 3 subcases.
i) If \(f(vw_1)=m-4\), then \(m-5\) cannot be placed, a contradiction.
ii) If \(f(w_1w_{r-1})=m-4\), then \(f(uw_{r-1})=m-6\), \(f(w_{r-1}w_r)=3\). Now, \(m-5\) cannot be placed, a contradiction.
iii) \(f(v)=m-4\). So, \(f(vw_1)=4\), \(f(vw_2)=m-5\). This forces \(f(w_1w_{r-1})=m-6\), \(f(w_{r-1})=6\) and \(f(uw_{r-1})=m-8\). Now the undetermined vertex labels are greater than 8 and smaller then \(m-8\). So \(m-7\) cannot be placed, a contradiction.
b) If \(f(w_2)=m-2\), then \(f(w_1w_2)=2, f(w_2w_r)=m-3\). Hence, \(m-4\) must be the label of an edge incident to \(w_1\). If \(f(w_1w_{r-1})=m-4\), then \(f(w_{r-1})=4, f(w_{r-1}w_r)=3, f(w_2w_{r-1})=m-6\). Now, \(m-5\) cannot be placed, a contradiction. If \(f(vw_1)=m-4\), then we also get a similar contradiction.
\(\square\)
In [8, Theorem 4.6], the authors showed that \(K(1,m,r)\) is super graceful for \(m,r\ge 1\).
Conjecture 3.6. For \(t\ge 3\), a complete \(t\)-partite graph \(G\) is \(k\)-super graceful if and only if \(G=K(1,m,r)\) and \(k=1\).
In [8, Construction C4], the authors gave a way to construct infinitely many super graceful bipartite graphs. The approach can be extended to obtained infinitely many \(k\)-super graceful bipartite graphs.
Approach A1. Begin with vertices \(u_i\) \((0\le i\le n)\). Choose an integer \(d > k\ge 1\).
(a) Label \(u_i\) by \(k+id\).
(b) For \(1\le j\le d-1\), add a vertex \(v_j\) and join it to each of \(u_i\).
(c) Label edge \(u_iv_j\) by \(k+j+(n-i)d\) and vertex \(v_j\) by \(2k+j+nd\).
(d) Delete edge \(u_iv_j\) if its label is also one of the vertex labels.
(e) For \(r=1,2,\ldots\), introduce \(d\) new vertices with labels \((r+2)k+(nr+n+r)d+s-1\), \(1\le s\le d\). Join each of them to each \(u_i\), \(0\le i\le n\). The induced edge labels are \((r+1)k+(nr+n+r-i)d+s-1\).
(f) Delete each new edge in (e) if its label is one of the new vertex labels.
Approach A2. Begin with integers \(u_i\) \((0\le i\le n)\). Choose an integer \(2\le d\le k\)
(a) Label \(u_i\) by \(k+id\).
(b) For \(1\le j\le k\), add a vertex \(v_j\) and join it to each of \(u_i\).
(c) Label edge \(u_iv_j\) by \(k+j+(n-i)d\) and vertex \(v_j\) by \(2k+j+nd\).
(d) In Step (c), if an edge label is also a vertex label, delete the corresponding edge. If a label is assigned to more than 1 edge, delete all but one of the edges.
(e) For \(r=1,2,\ldots\), introduce \(k\) new vertices with labels \(2(r+1)k+(r+1)d+s\), \(1\le s\le k\). Join each of them to each \(u_i\), \(0\le i\le n\). The induced edge labels are \((2r+1)k+rd+s\).
(f) In Step (e), if a label is assigned to more than 1 edge, delete all but one of the edges.
One can verify that the bipartite graphs we have thus obtained are \(k\)-super graceful. Moreover, adding and assigning appropriate labels to the edges \(v_1v_2, v_1v_3, \ldots, v_1v_{d-1}\) in Approach A1, and to the edges \(v_1v_2, v_1v_3, \ldots, v_1v_k\) in Approach A2 give us \(1\)-, \(2\)-, …, \((k-1)\)-super graceful tripartite graphs respectively.