Let \(G=(V,E)\) be a graph of order \(n\) without isolated vertices. A bijection \(f\colon V\rightarrow \{1,2,\dots,n\}\) is called a local distance antimagic labeling, if \(w(u)\not=w(v)\) for every edge \(uv\) of \(G\), where \(w(u)=\sum_{x\in N(u)}f(x)\). The local distance antimagic chromatic number \(\chi_{ld}(G)\) is defined to be the minimum number of colors taken over all colorings of \(G\) induced by local distance antimagic labelings of \(G\). The concept of Generalized Mycielskian graphs was introduced by Stiebitz [20]. In this paper, we study the local distance antimagic labeling of the Generalized Mycielskian graphs.
By a graph \(G=(V, E)\), we mean a finite, simple, undirected graph having neither multiple edges nor loops. For graph theoretic notations, we refer to Chartrand and Lesniak [4].
Hartsfield and Ringel [9] introduced the notion of antimagic labeling in 1990. A graph \(G\) is antimagic if the edges of \(G\) can be labeled by the numbers \(\{1,2,\dots,|E|\}\) such that the sums of the labels of the edges incident to each vertex (called the weight of a vertex) are all distinct. They conjectured that every connected graph with at least three vertices admits an antimagic labeling. They also made a weaker conjecture that every tree with at least three vertices admits an antimagic labeling. These two conjectures were partly shown to be correct by several authors, but they are still unsolved.
A vertex version of antimagic labeling of a graph was introduced in [11] as follows: a bijection \(f: V \rightarrow \{1,2,\dots,|V|\}\) is said to be distance antimagic labeling of \(G\) if all the vertices have distinct vertex weights, where the weight of a vertex is defined as \(w(v)=\sum_{x\in N(v)}f(x)\), where \(N(v)\) is the open neighborhood of the vertex \(v\), which is defined as the set of vertices of the graph \(G\) which are adjacent to \(v\). A graph \(G\) is called a distance antimagic graph if it admits a distance antimagic labeling \(f\).
Arumugam et al. [1] introduced a local version of antimagic labeling: let \(G=(V,E)\) be a graph. A bijection \(f\colon E\rightarrow \{1,2,\dots, |E|\}\) is called local antimagic labeling if for any two adjacent vertices \(u\) and \(v\), \(w(u)\not=w(v)\), where \(w(u)=\sum_{e\in E(u)}f(e)\) and \(E(u)\) is the set of edges incident to \(u\). Thus, any local antimagic labeling induces a proper vertex coloring of \(G\) where the vertex \(v\) is assigned the color \(w(v)\). The local antimagic chromatic number \(\chi_{la}(G)\) is the minimum number of colors taken over all colorings induced by local antimagic labelings of \(G\). Arumugam et al. [1] conjectured that a connected graph with at least three vertices admits a local antimagic labeling. Bensmail et al. [2] solved this conjecture partially. Finally, Haslegrave [10] proved this conjecture using probabilistic tools. Recently, several authors investigated the local antimagic chromatic number for several families of graphs. For further study ( see [1], 12, 13, 15).
Motivated by local antimagic labeling, Divya et al. [5] and Handa et al. [9] independently introduced the notion of local distance antimagic labeling as follows: let \(G=(V, E)\) be a graph of order \(n\) and let \(f\colon V\rightarrow\{1,2,\dots,n\}\) be a bijection. For every vertex \(v\in V\), define the weight of \(v\) as \(w(v)=\sum_{x\in N(u)}f(x)\). The labeling \(f\) is said to be a local distance antimagic labeling of \(G\) if \(w(u)\not=w(v)\) for every pair of adjacent vertices \(u,v\in V\). A graph that admits such a labeling is called a local distance antimagic graph. A local distance antimagic labeling induces a proper vertex coloring of the graph, with the vertex \(v\) assigned the color \(w(v)\). The local distance antimagic chromatic number \(\chi_{ld}(G)\) is the minimum number of colors taken over all colorings induced by local distance antimagic labelings of \(G\). Clearly \(\chi_{ld}(G) \geq \chi(G)\). Several authors have studied and found local distance antimagic chromatic numbers for different classes of graphs. For further study (see [5, 6, 16, 17, 18, 19]).
Among all the constructions available for a triangle-free graph with the chromatic number increasing by one in the literature, the Mycielskian construction is one of the simplest [14]. Given a triangle-free graph \(G=(V,E)\), the Mycielskian graph \(\mu(G)\) of \(G\) is a graph with the vertex set \(V(\mu(G))=\{ (x,0)(x,1);\ x\in V(G))\}\cup \{u\}\) and edge set \(E(\mu(G))=\{(x,0)(y,0), (x,1)(y,1);\ xy\in E(G)\}\cup \{(x,1)u;\ x\in V(G)\}\). The construction preserves the property of being triangle-free but increases the chromatic number by one. By applying the construction repeatedly to a triangle-free graph, Mycielskian [14] showed that there exist triangle-free graphs with arbitrarily large chromatic numbers.
Stiebitz [20] generalized Mycielski’s construction in the following way: Given a graph \(G=(V,E)\) and an integer \(t\geq 0\), the Generalized Mycielskian graph \(\mu_{t}(G)\) is a graph with vertex set \(\{(x,i):\ 0\leq i \leq t,\ x\in V(G)\}\cup\{u\}\), where there is an edge \((x,0)(y,0)\) and \((x,i)(y,i+1)\) whenever there is an edge \(xy\in E(G)\) and an edge \((x,t)u\) for all \(x\in V(G)\). Observe that, for a connected graph \(G\) with \(|V(G)|=n\), \(\mu_t(G)\) is also connected with \(|V(\mu_t(G))|=(t+1)n+1\). Note that \(\mu_0(G)\approx G\) and \(\mu_1(G)\approx \mu(G)\). The construction for \(\mu_2(C_6)\) is illustrated in Figure 1 ahead.
In this article, we study the local distance antimagic labeling of the Generalized Mycielskian construction of graphs and provide an upper bound for the local distance antimagic chromatic number of such graphs. We assume that all graphs \(G\), considered in this article, are local distance antimagic with local distance antimagic chromatic number \(\chi_{ld}(G)\).
In our investigation, we also require the concept of the magic rectangle and the nearly magic rectangle. A magic rectangle \(MR(a,b)=(m_{i,j})\) is an \(a\times b\) array with entries \(1,2,\dots, ab,\) each appearing once, with all its row sums equal to a constant \(\rho\) and all its column sums equal to a constant \(\sigma\). The sum of the entries in \(MR(a,b)\) is \(\frac{ab(ab+1)}{2}\) and the magic constants are \[\begin{aligned} \sigma=\sum_{i=1}^am_{ij}=\frac{a(ab+1)}{2}, &\text{ for any $j\in \{1,2,\dots,b\}$, \qquad \text{and} }\\ \rho=\sum_{j=1}^bm_{ij}=\frac{b(ab+1)}{2}, &\text{ for any $i\in \{1,2,\dots,a\}$.} \end{aligned}\]
Harmuth [7, 8] proved that such arrays exist whenever \(a\) and \(b\) are of the same parity, except when exactly one of \(a\) and \(b\) is \(1\), or \(a=b=2\).
Theorem 1.1. [7, 8] A magic rectangle \(MR(a,b)\) exists if and only if \(a,b>1\), \(ab>4\) and \(a\equiv b\ (\bmod\ 2)\).
When \(a\) and \(b\) are of different parity, the magic rectangle \(MR(a,b)\) does not exist. Chai et al. [3] introduced the concept of the nearly magic rectangle. A nearly magic rectangle \(NMR(a,b)\) is defined as an \(a\times b\) array with \(a\) odd and \(b\) even that contains each of the integers from the set \(\{1,2,\dots,ab\}\) exactly once and the row sums are constants while the column sums differ by at most one. The following results are from [3].
Theorem 1.2. [3] Let \(b\geq 3\) be odd. Then there exists a \(b\times 2\) nearly magic rectangle.
Theorem 1.3. [3] Let \(a\geq 3\) be odd and \(b\equiv 2\ (\bmod\ 4)\), \(b\geq 6\). Then, there exists a nearly magic rectangle of order \(a\times b\).
Theorem 1.4. [3] Let \(a\geq 3\) be odd and \(b\equiv 0\ (\bmod\ 4)\), \(b\geq 6\). Then, there exists a nearly magic rectangle of order \(a\times b\).
Lemma 2.1. Let \(t>1\) be an odd positive integer and \(G\) be an \(r\)-regular graph of order \(n\). Then \[\begin{aligned} \chi_{ld}(\mu_{t}(G))\leq \begin{cases} 2\chi_{ld}(G)+t &\text{for $t<5$,}\\ 2\chi_{ld}(G)+t-1 &\text{for $t\geq 5$.} \end{cases} \end{aligned}\]
Proof. Let \(V(G)=\{v_1,v_2,\dots,v_n\}\) be the vertex set of \(G\) and \(g\) be a local distance antimagic labeling of \(G\) that assigns \(\chi_{ld}(G)\) distinct weights to the vertices of \(G\). Let \(H=\mu_{t}(G)\). Define a bijection \(f\colon V(H)\rightarrow \{1,2,\dots,n(t+1),n(t+1)+1\}\) by \(f(u)=1\), and for \(v\in V(G)\) and \(0\leq i \leq t\), \[\begin{aligned} f(v,t-i)&= \begin{cases} tn+1+g(v) &\text{for $i=0$,}\\ (i-1)n+1+g(v) &\text{for $i\equiv 0,1\ (\bmod\ 4)$, $i\not=0$,}\\ in+2-g(v) &\text{for $i\equiv 2,3\ (\bmod\ 4)$.} \end{cases} \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{v\in V(G)}f(v,t)=\sum_{v\in V(G)}\big(tn+1+g(v)\big)\\ &=(tn+1)n+\frac{n(n+1)}{2}\\ &=tn^2+\frac{n^2+3n}{2}. \end{aligned}\]
The weight of vertices \((v,t)\) and \((v,t-1)\), for \(v\in V(G)\), are \[\begin{aligned} w(v,t)&=f(u)+\sum_{x\in N_G(v)}f(x,t-1)\\ &=1+\sum_{x\in N_G(v)}\big(1+g(x)\big)\\ &=1+r+w_g(v),\\ w(v,t-1)&=\sum_{x\in N_G(v)}f(x,t-2)+\sum_{x\in N_G(v)}f(x,t)\\ &=\sum_{x\in N_G(v)}\big(2n+2-g(x)\big)+\sum_{x\in N_G(v)}\big(tn+1+g(x)\big)\\ &=(2n+2)r-w_g(v)+(tn+1)r+w_g(v)\\ &=\big((t+2)n+3\big)r. \end{aligned}\]
For the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t\) and \(i\equiv 1\ (\bmod\ 4)\), we obtain \[\begin{aligned} w(v,t-i)&=\sum_{x\in N_G(v)}f(x,t-i-1)+\sum_{x\in N_G(v)}f(x,t-i+1)\\ &=\sum_{x\in N_G(v)}\big((i+1)n+2-g(x)\big)+\sum_{x\in N_G(v)}\big((i-2)n+1+g(x)\big)\\ &=\big((i+1)n+2\big)r-w_g(v)+\big((i-2)n+1\big)r+w_g(v)\\ &=\big((2i-1)n+3\big)r. \end{aligned}\]
Similarly, the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t\) and \(i\equiv 2,3,4\ (\bmod\ 4)\) is \(w(v,t-i)=\big((2i-1)n+3\big)r\). Note that the weight of the vertex \((v,0)\), for \(v\in V(G)\), depends on the nature of \(t\). \[\begin{aligned} w(v,0)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,1)\\ &=\begin{cases} \displaystyle\sum_{x\in N_G(v)}\big((t-1)n+1+g(x)\big)+\displaystyle\sum_{x\in N_G(v)}\big((t-2)n+1+g(x)\big) &\text{ if $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\sum_{x\in N_G(v)}\big(tn+2-g(x)\big)+\displaystyle\sum_{x\in N_G(v)}\big((t-1)n+2-g(x)\big) &\text{ if $t\equiv 3\ (\bmod\ 4)$,}\\ \end{cases}\\ &=\begin{cases} \big((2t-3)n+2\big)r+2W_g(v) &\text{ if $t\equiv 1\ (\bmod\ 4)$,}\\ \big((2t-1)n+4\big)r-2W_g(v) &\text{ if $t\equiv 3\ (\bmod\ 4)$.} \end{cases} \end{aligned}\]
We shall now show that adjacent vertices of \(H\) have distinct weights. First note that, as \(G\) is an \(r\)-regular graph, for any vertex \(v\in V(G)\), \(w_g(v)\leq n+n-1+n-2+\dots+n-(r-1)=nr-\frac{(r-1)r}{2}<nr\) and \(w_g(v)\geq 1+2+3+\dots+r=\frac{r(r+1)}{2}.\)
If suppose \(w(u)=w(v,t)\) for some \(v\in V(G)\), then we obtain, \(w_g(v)=tn^2+\frac{n^2+n}{2}+n-1-r>tn^2>nr\), which is a contradiction. Further, if for some vertex \(v\in V(G)\), \(w(v,t)=w(v,t-1)\), then we have \(1+r+w_g(v)=\big((t+2)n+3\big)r\), which implies \(w_g(v)=\big((t+2)n+2\big)r-1\geq (t+2)nr>nr\), a contradiction. Therefore, \(w(u)\not=w(v,t)\) and \(w(v,t)\not=w(v,t-1)\) for any \(v\in V(G)\). Also, it is easy to see that, as \(t>1\), \(w(v,t-1)\not=w(v,t-2)\) for all \(v\in V(G)\). Similarly, for \(2\leq i\leq t-2\), it is easy to verify that \(w(v,t-i)\not=w(v,t-(i+1))\) for all \(v\in V(G)\).
Now if \(t\equiv 1\ (\bmod\ 4)\) and \(w(v,0)=w(v,1)\) for some vertex \(v\in V(G)\), then we obtain \(\big((2t-3)n+2\big)r+2w_g(v)=\big((2t-3)n+3\big)r,\) implying \(w_g(v)=\frac{r}{2}\), a contradiction as \(w_g(v)\geq \frac{r(r+1)}{2}.\) Also, if \(t\equiv 3\ (\bmod\ 4)\) and \(w(v,0)=w(v,1)\) for some vertex \(v\in V(G)\), then we obtain \(\big((2t-1)n+4\big)r-2w_g(v)=\big((2t-3)n+3\big)r,\) implying \(w_g(v)=\frac{(2n+1)r}{2}>nr\), a contradiction. Hence, in either case, \(w(v,0)\not=w(v,1)\) for all \(v\in V(G)\). Also, as \(g\) is a local distance antimagic labeling of \(G\), the adjacent vertices among \((v,0)\) have distinct weights. This shows that all adjacent vertices of \(H\) have distinct weights, and hence \(f\) is a local distance antimagic labeling of \(H\) that assigns \(2\chi_{ld}(G)+t\) distinct weights to vertices of \(H\). Note that, if \(t\geq 5\), then for \(i=\frac{t+3}{2}\), \(w(v,t-1)=w(v,t-i)\), for all \(v\in V(G)\). Therefore for \(t\geq 5\), \(f\) assigns \(2\chi_{ld}(G)+t-1\) distinct weights to vertices of \(H\). This concludes the proof. ◻
Lemma 2.2. Let \(t>2\) be even and \(G\) be an \(r\)-regular graph of order \(n\). Then \[\chi_{ld}(\mu_{t}(G))\leq2\chi_{ld}(G)+t.\]
Proof. Let \(V(G)=\{v_1,v_2,\dots,v_n\}\) be the vertex set of \(G\) and \(g\) be a local distance antimagic labeling of \(G\) that assigns \(\chi_{ld}(G)\) distinct weights to the vertices of \(G\). Let \(H=\mu_{t}(G)\). We shall provide a labeling for the vertices of \(H\) in two cases depending upon the nature of \(t\).
[Case 1.] If \(t\equiv 2\ (\bmod 4)\).
Define a bijection \(f\colon V(H)\rightarrow \{1,2,\dots,n(t+1),n(t+1)+1\}\) by \(f(u)=1\), and for \(v\in V(G)\) and \(0\leq i \leq t,\) \[\begin{aligned} f(v,t-i)&= \begin{cases} (t+1)n+2-g(v) &\text{for $i=0$,}\\ in+1+g(v) &\text{for $i\equiv 1,2\ (\bmod\ 4)$, $i\not=t,t-1$,}\\ (i+1)n+2-g(v) &\text{for $i\equiv 3,4\ (\bmod\ 4)$, $i\not=0$,}\\ 1+g(v) &\text{for $i=t-1$,}\\ (t-1)n+1+g(v) &\text{for $i=t$.} \end{cases} \end{aligned}\] The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{v\in V(G)}f(v,t)=\sum_{v\in V(G)}\big((t+1)n+2-g(v)\big)\\ &=\big((t+1)n+2\big)n-\frac{n(n+1)}{2}\\ &=tn^2+\frac{n^2+3n}{2}. \end{aligned}\] The weight of vertices \((v,t)\), \((v,t-1)\), \((v,2)\), \((v,1)\) and \((v,0)\), for \(v\in V(G)\) are \[\begin{aligned} w(v,t)&=f(u)+\sum_{x\in N_G(v)}f(x,t-1)\\ &=1+\sum_{x\in N_G(v)}\big(1+n+g(x)\big)\\ &=1+(1+n)r+w_g(v),\\ w(v,t-1)&=\sum_{x\in N_G(v)}f(x,t-2)+\sum_{x\in N_G(v)}f(x,t)\\ &=\sum_{x\in N_G(v)}\big(2n+1+g(x)\big)+\sum_{x\in N_G(v)}\big((t+1)n+2-g(x)\big)\\ &=(2n+1)r+w_g(v)+\big((t+1)n+2\big)r-w_g(v)\\ &=\big((t+3)n+3\big)r,\\ w(v,2)&=\sum_{x\in N_G(v)}f(x,1)+\sum_{x\in N_g(v)}f(x,3)\\ &=\sum_{x\in N_G(v)}\big(1+g(x)\big)+\sum_{x\in N_g(v)}\big((t-2)n+2-g(x)\big)\\ &=r+w_g(v)+\big((t-1)n+2\big)r-w_g(v)\\ &=\big((t-2)n+3\big)r,\\ w(v,1)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_g(v)}f(x,2)\\ &=\sum_{x\in N_G(v)}\big((t-1)n+1+g(x)\big)+\sum_{x\in N_g(v)}\big((t-1)n+2-g(x)\big)\\ &=\big((t-1)n+1\big)r+w_g(v)+\big((t-1)n+2\big)r-w_g(v)\\ &=\big((2t-2)n+3\big)r,\\ w(v,0)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,1)\\ &=\sum_{x\in N_G(v)}\big((t-1)n+1+g(x)\big)+\sum_{x\in N_G(v)}\big(1+g(x)\big)\\ &=\big((t-1)n+1\big)r+w_g(v)+r+w_g(v)\\ &=\big((t-1)n+2\big)r+2w_g(v). \end{aligned}\] For the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t-2\) and \(i\equiv 1\ (\bmod\ 4)\), we obtain ‘\[\begin{aligned} w(v,t-i)&=\sum_{x\in N_G(v)}f(x,t-i-1)+\sum_{x\in N_G(v)}f(x,t-i+1)\\ &=\sum_{x\in N_G(v)}\big((i+1)n+1+g(x)\big)+\sum_{x\in N_G(v)}\big(in+2-g(x)\big)\\ &=\big((i+1)n+1\big)r+w_g(v)+\big(in+2\big)r-w_g(v)\\ &=\big((2i+1)n+3\big)r. \end{aligned}\] Similarly, the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t-2\) and \(i\equiv 2,3,4\ (\bmod\ 4)\) is \(w(v,t-i)=\big((2i+1)n+3\big)r\).
Case 2. If \(t\equiv 0\ (\bmod\ 4)\).
Define a bijection \(f\colon V(H)\rightarrow \{1,2,\dots,n(t+1),n(t+1)+1\}\) by \(f(u)=1\), and for \(v\in V(G)\) and \(0\leq i \leq t,\) \[\begin{aligned} f(v,t-i)&= \begin{cases} (t+1)n+2-g(v) &\text{for $i=0$,}\\ in+1+g(v) &\text{for $i\equiv 1,2\ (\bmod\ 4)$,}\\ (i+1)n+2-g(v) &\text{for $i\equiv 3,4\ (\bmod\ 4)$, $i\not=0,t,t-1$,}\\ n+2-g(v) &\text{for $i=t-1$,}\\ tn+2-g(v) &\text{for $i=t$.}\\ \end{cases} \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{v\in V(G)}f(v,t)=\sum_{v\in V(G)}\big((t+1)n+2-g(v)\big)\\ &=\big((t+1)n+2\big)n-\frac{n(n+1)}{2}\\ &=tn^2+\frac{n^2+3n}{2}. \end{aligned}\]
The weight of vertices \((v,t)\), \((v,t-1)\), \((v,2)\), \((v,1)\) and \((v,0)\), for \(v\in V(G)\) are \[\begin{aligned} w(v,t)&=f(u)+\sum_{x\in N_G(v)}f(x,t-1)\\ &=1+\sum_{x\in N_G(v)}\big(1+n+g(x)\big)\\ &=1+(1+n)r+w_g(v), \end{aligned}\] \[\begin{aligned} w(v,t-1)&=\sum_{x\in N_G(v)}f(x,t-2)+\sum_{x\in N_G(v)}f(x,t)\\ &=\sum_{x\in N_G(v)}\big(2n+1+g(x)\big)+\sum_{x\in N_G(v)}\big((t+1)n+2-g(x)\big)\\ &=(2n+1)r+w_g(v)+\big((t+1)n+2\big)r-w_g(v)\\ &=\big((t+3)n+3\big)r,\\ w(v,2)&=\sum_{x\in N_G(v)}f(x,1)+\sum_{x\in N_g(v)}f(x,3)\\ &=\sum_{x\in N_G(v)}\big(n+2-g(x)\big)+\sum_{x\in N_g(v)}\big((t-3)n+1+g(x)\big)\\ &=(n+2)r-w_g(v)+\big((t-3)n+1\big)r+w_g(v)\\ &=\big((t-2)n+3\big)r,\\ w(v,1)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_g(v)}f(x,2)\\ &=\sum_{x\in N_G(v)}\big(tn+2-g(x)\big)+\sum_{x\in N_g(v)}\big((t-2)n+1+g(x)\big)\\ &=(tn+2)r-w_g(v)+\big((t-2)n+1\big)r+w_g(v)\\ &=\big((2t-2)n+3\big)r,\\ w(v,0)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,1)\\ &=\sum_{x\in N_G(v)}\big(tn+2-g(x)\big)+\sum_{x\in N_G(v)}\big(n+2-g(x)\big)\\ &=\big(tn+2\big)r-w_g(v)+(n+2)r-w_g(v)\\ &=\big((t+1)n+4\big)r-2w_g(v). \end{aligned}\]
For the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t-2\) and \(i\equiv 1\ (\bmod\ 4)\), we obtain \[\begin{aligned} w(v,t-i)&=\sum_{x\in N_G(v)}f(x,t-i-1)+\sum_{x\in N_G(v)}f(x,t-i+1)\\ &=\sum_{x\in N_G(v)}\big((i+1)n+1+g(x)\big)+\sum_{x\in N_G(v)}\big(in+2-g(x)\big)\\ &=\big((i+1)n+1\big)r+w_g(v)+\big(in+2\big)r-w_g(v)\\ &=\big((2i+1)n+3\big)r. \end{aligned}\]
Similarly, the weight of the vertex \((v,t-i)\), for \(v\in V(G)\), \(1<i<t-2\) and \(i\equiv 2,3,4\ (\bmod\ 4)\) is \(w(v,t-i)=\big((2i+1)n+3\big)r\).
We shall now show that, in either case, the adjacent vertices of \(H\) have different weights. As shown in Lemma 2.1, since \(G\) is an \(r\)-regular graph, for any vertex \(v\in V(G)\), \(w_g(v)<nr\) and \(w_g(v)\geq \frac{r(r+1)}{2}\). Now, if suppose \(w(u)=w(v,t)\) for some \(v\in V(G)\), then we obtain \(w_g(v)+nr=tn^2+\frac{n^2+3n}{2}-1-r>tn^2>2nr\), as \(t>2\). But, as \(w_g(v)<nr\), we should have \(w_g(v)+nr<2nr\), which is not the case. Therefore \(w(u)\not=w(v,t)\) for any \(v\in V(G)\). Further, if for some vertex \(v\in V(G)\), \(w(v,t)=w(v,t-1)\), then we have \(1+(1+n)r+w_g(v)=\big((t+3)n+3\big)r\), which implies \(w_g(v)=\big((t+2)n+2\big)r-1\geq (t+2)nr>nr\), a contradiction. Hence, \(w(v,t)\not=w(v,t-1)\) for all \(v\in V(G)\). As \(t>2\), \(w(v,t-1)\not=w(v,t-2)\) for any vertex \(v\in V(G)\), as \(\big((t+3)n+3\big)r\not=(5n+3)r\). Clearly, for any vertex \(v\in V(G)\), \(w(v,t-i)\not=w(v,t-(i+1))\) for \(2\leq i \leq t-4\). Also, for any \(v\in V(G)\), \(w(v,3)\not=w(v,2)\) as \(\big((2t-5)n+3\big)r\not=\big((t-2)n+3\big)r\). Similarly, one can clearly see that for any \(v\in V(G)\), \(w(v,1)\not=w(v,2)\) as \(\big((t-2)n+3\big)r\not=\big((2t-2)n+3\big)r\). Consider the case when \(t\equiv 0\ (\bmod\ 4)\). If suppose \(w(v,1)=w(v,0)\) for some \(v\in V(G)\), then we have \(\big((2t-2)n+3\big)r=\big((t+1)n+4\big)r-2w_g(v)\), which implies, \(2w_g(v)=(3-t)nr+r\). But as \(t>2\) and \(t\equiv 0\ (\bmod\ 4)\), we get \(w_g(v)<0\), a contradiction. Similarly, for the case when \(t\equiv 2\ (\bmod\ 4)\), if \(w(v,1)=w(v,0)\) for some \(v\in V(G)\), then we have \(\big((2t-2)n+3\big)r=\big((t-1)n+2\big)r+2w_g(v)\), which implies \(2w_g(v)=\big((t-1)n+1\big)r>2nr\) as \(t\equiv 2\ (\bmod\ 4)\) and \(t>2\). Hence, in either case, \(w(v,1)\not=w(v,0)\) for any \(v\in V(G)\). Also, as \(g\) is a local distance antimagic labeling of \(G\), the adjacent vertices among \((v,0)\) have different weights. This shows that in either case, all adjacent vertices of \(H\) have different weights, and hence \(f\) is a local distance antimagic labeling of \(H\) that assigns \(2\chi_{ld}(G)+t\) distinct weights to its vertices. This concludes the proof. ◻
Lemma 2.3. <For an \(r\)-regular graph \(G\) of order \(n\), we have \(\chi_{ld}(\mu_2(G))\leq 2 \chi_{ld}(G)+2\).
Proof. Let \(V(G)=\{v_1,v_2,\dots,v_n\}\) be the vertex set of \(G\) and \(g\) be a local distance antimagic labeling of \(G\) that assigns \(\chi_{ld}(G)\) distinct weights to the vertices of \(G\). Let \(H=\mu_{2}(G)\). Define a bijection \(f\colon V(H)\rightarrow\{1,2,\dots 3n+1\}\) by \(f(u)=1\), and for \(v\in V(G)\), \[\begin{aligned} f(v,i)&= \begin{cases} n+1+g(v) &\text{for $i=0$,}\\ 1+g(v) &\text{for $i=1$,}\\ 3n+2-g(v)&\text{for $i=2$.} \end{cases} \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{v\in V(G)}f(v,2)=\sum_{v\in V(G)}\big(3n+2-g(v)\big)\\ &=(3n+2)n-\frac{n(n+1)}{2}\\ &=\frac{5n^2+3n}{2}. \end{aligned}\]
The weight of vertices \((v,2)\), \((v,1)\) and \((v,0)\), for \(v\in V(G)\) are \[\begin{aligned} w(v,2)&=\sum_{x\in N_G(v)}f(x,1)+f(u)\\ &=\sum_{x\in N_G(v)}\big(1+g(x)\big)+1\\ &=r+1+w_g(v), \\ w(v,1)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,2)\\ &=\sum_{x\in N_G(v)}\big(n+1+g(x)\big)+\sum_{x\in N_G(v)}\big(3n+2-g(x)\big)\\ &=(n+1)r+w_g(v)+(3n+2)r-w_g(v)\\ &=(4n+3)r,\\ w(v,0)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,1)\\ &=\sum_{x\in N_G(v)}(n+1+g(x))+\sum_{x\in N_G(v)}(1+g(x))\\ &=(n+1)r+w_g(v)+r+w_g(v)\\ &=(n+2)r+2w_g(v). \end{aligned}\]
Using the approach as used in Lemma 2.1 and Lemma 2.2, it is easy to show that \(w(u)\not=w(v,2)\), \(w(v,2)\not=w(v,1)\) and \(w(v,1)\not=w(v,0)\) for any \(v\in V(G)\). Also, as \(g\) is a local distance antimagic labeling of \(G\), the adjacent vertices among \((v,0)\) have different weights. This shows that \(f\) is a local distance antimagic labeling of \(H\) that assigns \(2\chi_{ld}+2\) distinct weights to its vertices. ◻
After obtaining the upper bounds on the local distance antimagic chromatic number of the Generalized Mycielskian construction of regular graphs, we now turn to obtain an upper bound on the local distance antimagic chromatic number of the Mycielskian construction of regular graphs. As described in the introduction, we will make sure to note the Mycielskian construction of a graph \(G\) by \(\mu(G)\).
Lemma 2.4. For an \(r\)-regular graph \(G\) of order \(n\), we have \(\chi_{ld}(\mu(G))\leq 2 \chi_{ld}(G)+1\).
Proof. Let \(V(G)=\{v_1,v_2,\dots,v_n\}\) be the vertex set of \(G\) and \(g\) be a local distance antimagic labeling of \(G\) that assigns \(\chi_{ld}(G)\) distinct weights to the vertices of \(G\). Let \(H=\mu(G)\). Define a bijection \(f\colon V(H)\rightarrow\{1,2,\dots 2n+1\}\) by \(f(u)=1\), and for \(v\in V(G)\), \[\begin{aligned} f(v,i)&= \begin{cases} 1+g(v) &\text{for $i=0$,}\\ 1+n+g(v) &\text{for $i=1$.} \end{cases} \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{v\in V(G)}f(v,1)=\sum_{v\in V(G)}\big(1+n+g(v)\big)\\ &=n(n+1)+\frac{n(n+1)}{2}\\ &=\frac{3n(n+1)}{2}. \end{aligned}\]
The weight of vertices \((v,1)\) and \((v,0)\), for \(v\in V(G)\) are \[\begin{aligned} w(v,1)&=\sum_{x\in N_G(v)}f(x,0)+f(u)\\ &=\sum_{x\in N_G(v)}\big(1+g(x)\big)+1\\ &=r+1+w_g(v), \\ w(v,0)&=\sum_{x\in N_G(v)}f(x,0)+\sum_{x\in N_G(v)}f(x,1)\\ &=\sum_{x\in N_G(v)}(1+g(x))+\sum_{x\in N_G(v)}(1+n+g(x))\\ &=r+w_g(v)+(1+n)r+w_g(v)\\ &=(n+2)r+2w_g(v). \end{aligned}\]
Clearly \(w(u)\not=w(v,1)\) for all \(v\in V(G)\). Now, if for some adjacent vertices \(u\) and \(v\) of \(G\), we have \(w(u,1)=w(v,0)\), then we have \(r+1+w_g(u)=(n+2)r+2w_g(v)\), which implies \(1-(1+n)r=2w_g(v)-w_g(u)\). As \(g\) is an \(r\)-regular graph, \(w_g(v)\geq \frac{r(r+1)}{2}\) and \(w_g(u)\leq nr-\frac{r(r-1)}{2}\). Therefore \(2w_g(v)-w_g(u)\geq \frac{2r(r+1)}{2}-nr+\frac{r(r-1)}{2}=\frac{3r(r+1)}{2}-nr\). But \(1-(1+n)r<\frac{3r(r+1)}{2}-nr\), which is a contradiction. Hence, \(w(u,1)\not=w(v,0)\), for any pair of adjacent vertices \(u,v\in V(G)\). Also, as \(g\) is a local distance antimagic labeling of \(G\), the adjacent vertices among \((v,0)\) have different weights. This shows that \(f\) is a local distance antimagic labeling of \(H\) that assigns \(2\chi_{ld}+1\) distinct weights to its vertices. ◻
The four lemmas proven above can be combined in the form of the following theorem.
Theorem 2.5. Let \(t\) be a positive integer and \(G\) be an \(r\)-regular graph. Then \[\begin{aligned} \chi_{ld}(\mu_{t}(G))\leq \begin{cases} 2\chi_{ld}(G)+t &\text{for odd $t<5$ and even $t$,}\\ 2\chi_{ld}(G)+t-1 &\text{for odd $t\geq 5$.} \end{cases} \end{aligned}\]
Note that Theorem 2.5 provides an upper bound for the local distance antimagic chromatic number of the Generalized Myceilskian construction \(\mu_t(G)\), of a regular graph \(G\). However, these bounds can still be improved for some graphs, as shown in the following example.
Theorem 2.6. For integers \(t,m,n>1\), we have \(3\leq \chi_{ld}\big(\mu_t(K_{m,n})\big)\leq 5\).
Proof. Let \(V(K_{m,n})=\{x_1,x_2,\dots,x_m\}\cup\{y_1,y_2,\dots,y_n\}\) be the vertex set of \(K_{m,n}\). Assume \(m\leq n\) and let \(H=\mu_t(K_{m,n})\). Depending on the parity of \(t\), \(m\), and \(n\), we provide different labelings for the vertices of \(H\) such that the labeling induces five different weights on the vertices of \(H\).
Case 1. \(m\) and \(n\) both even.
Define a bijection \(f\colon V(H)\rightarrow\{1,2,3,\dots,(m+n)(t+1), (m+n)(t+1)+1\}\) by \(f(u)=1\), and for \(0\leq j \leq t\), \[\begin{aligned} f(x_i,j)&= \begin{cases} (i-1)(t+1)+2+j &\text{for $i=1,3,5,\dots,m-1$, }\\ i(t+1)+1-j &\text{for $i=2,4,6,\dots,m$, } \end{cases}\\ f(y_{i},j)&= \begin{cases} m(t+1)+(i-1)(t+1)+2+j &\text{for $i=1,3,5,\dots,n-1$,}\\ m(t+1)+i(t+1)+1-j &\text{for $i=2,4,6,\dots,n$.}\\ \end{cases} \end{aligned}\] Note that for any fixed \(j\in \{0,1,2\dots,t\}\), \[\begin{aligned} \sum_{i=1}^nf(y_i,j)&=\sum_{k=1}^{\frac{n}{2}}f(y_{2k},j)+\sum_{k=1}^{\frac{n}{2}}f(y_{2k-1},j)\\ &=\sum_{k=1}^{\frac{n}{2}}\big(m(t+1)+2k(t+1)+1-j\big)+\sum_{k=1}^{\frac{n}{2}}\big(m(t+1)+2(k-1)(t+1)+2+j\big)\\ &=\frac{\big(m(t+1)+1-j\big)n}{2}+\frac{n(t+1)}{2}\bigg(\frac{n}{2}+1\bigg)+\frac{\big(m(t+1)+2+j\big)n}{2}\\&\quad+\frac{n(t+1)}{2}\bigg(\frac{n}{2}-1\bigg)\\ &=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2},\\ \sum_{i=1}^nf(x_i,j)&=\sum_{k=1}^{\frac{m}{2}}f(x_{2k},j)+\sum_{k=1}^{\frac{m}{2}}f(x_{2k-1},j)\\ &=\sum_{k=1}^{\frac{m}{2}}\big(2k(t+1)+1-j\big)+\sum_{k=1}^{\frac{m}{2}}\big(2(k-1)(t+1)+2+j\big)\\ &=\frac{\big(1-j\big)m}{2}+\frac{m(t+1)}{2}\bigg(\frac{m}{2}+1\bigg)+\frac{\big(2+j\big)m}{2}+\frac{m(t+1)}{2}\bigg(\frac{m}{2}-1\bigg)\\ &=\frac{m^2(t+1)}{2}+\frac{3m}{2}. \end{aligned}\]
For the weight of vertices \((x_p,j)\), where \(1\leq p \leq m\) and \(1\leq j \leq t-1\) and vertices \((y_q,j)\), where \(1\leq q \leq n\) and \(1\leq j \leq t-1\), we obtain \[\begin{aligned} w(x_p,j)&=\sum_{i=1}^nf(y_i,j-1)+\sum_{i=1}^nf(y_i,j+1)=2\bigg[\frac{\big(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\bigg] \\ &=(n^2+2mn)(t+1)+3n,\\ w(y_q,j)&=\sum_{i=1}^mf(x_i,j-1)+\sum_{i=1}^mf(x_i,j+1)=2\bigg[\frac{3m}{2}+\frac{m^2(t+1)}{2}\bigg]\\ &=m^2(t+1)+3m. \end{aligned}\]
The weight of vertices \((x_p,0)\), \((x_p,t)\) where \(1\leq p \leq m\) and vertices \((y_q,0)\), \((y_q,t)\) where \(1\leq q \leq n\) are \[\begin{aligned} w(x_p,0)&=\sum_{i=1}^nf(y_i,0)+\sum_{i=1}^nf(y_i,1)=(n^2+2mn)(t+1)+3n,\\ w(x_p,t)&=\sum_{i=1}^nf(y_i,t-1)+f(u)=\frac{\big(n^2+2mn\big)(t+1)}{2}+\frac{3n}{2}+1,\\ w(y_q,0)&=\sum_{i=1}^nf(x_i,0)+\sum_{i=1}^nf(x_i,1)=m^2(t+1)+3m,\\ w(y_q,t)&=\sum_{i=1}^mf(x_i,t-1)+f(u)=\frac{m^2(t+1)}{2}+\frac{3m}{2}+1. \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{i=1}^mf(x_i,t)+\sum_{i=1}^nf(y_i,t)=\frac{m^2(t+1)}{2}+\frac{3m}{2}+\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\\ &=\frac{(n+m)^2(t+1)}{2}+\frac{3(m+n)}{2}. \end{aligned}\]
Note that for \(1\leq p \leq m\) and \(1\leq q \leq n\), \(w(x_p,0)>w(y_q,0)\). Also, \(w(x_p,j)>w(y_q,j-1)\), \(w(x_p,j)>w(y_q,j+1)\), \(w(y_q,j)<w(x_p,j-1)\) and \(w(y_q,j)<w(x_p,j+1)\) for \(1\leq j \leq t-2\). Further, \(w(x_p,t-1)\not=w(y_q,t)\) and \(w(x_p,t)\not=w(y_q,t-1)\). Clearly \(w(u)>w(x_p,t)>w(y_q,t)\). Therefore, adjacent vertices of \(H\) have different weights, and therefore, \(f\) is a local distance antimagic labeling of \(H\) that assigns five distinct weights to its vertices.
Case 2. \(t\) even and \(m,n\) both odd.
As \((t+1)\equiv m\ (\bmod\ 2)\), by Theorem 1.1 there exists a magic rectangle \(A=(a_{i,j})\) having \(m\) rows and \((t+1)\) columns with row sum\(=\frac{(t+1)(m(t+1)+1)}{2}\) and column sum\(=\frac{m(m(t+1)+1)}{2}\). Similarly, as \(n\) is odd, there exists a magic rectangle \(B=(b_{i,j})\) having \(n\) rows and \((t+1)\) columns with row sum\(=\frac{(t+1)(n(t+1)+1)}{2}\) and column sum\(=\frac{n(n(t+1)+1)}{2}\). We use these magic rectangles to label \(H\). Define a bijection \(f\colon V(H)\rightarrow\{1,2,\dots, (m+n)(t+1), (m+n)(t+1)+1\}\) by \(f(u)=1\), and for \(0\leq j \leq t\), \[\begin{aligned} f(x_i,j)&=a_{i,j+1}+1 &\text{for $i=1,2,\dots,m$, }\\ f(y_i,j)&=b_{i,j+1}+m(t+1)+1 &\text{for $i=1,2,\dots,n$. } \end{aligned}\]
For the weight of vertices \((x_p,j)\), where \(1\leq p \leq m\) and \(1\leq j \leq t-1\) and vertices \((y_q,j)\), where \(1\leq q \leq n\) and \(1\leq j \leq t-1\), we obtain \[\begin{aligned} w(x_p,j)&=\sum_{i=1}^n f(y_i,j-1)+\sum_{i=1}^nf(y_i,j+1)\\ &=\sum_{i=1}^n\big(b_{i,j}+m(t+1)+1\big)+\sum_{i=1}^n\big(b_{i,j+2}+m(t+1)+1\big)\\ &=\frac{n\big(n(t+1)+1\big)}{2}+mn(t+1)+n+\frac{n\big(n(t+1)+1\big)}{2}+mn(t+1)+n\\ &=(n^2+2mn)(t+1)+3n,\\ w(y_q,j)&=\sum_{i=1}^m f(x_i,j-1)+\sum_{i=1}^mf(x_i,j+1)\\ &=\sum_{i=1}^m\big(a_{i,j}+1\big)+\sum_{i=1}^m\big(a_{i,j+2}+1\big)\\ &=\frac{m\big(m(t+1)+1\big)}{2}+m+\frac{m\big(m(t+1)+1\big)}{2}+m\\ &=m^2(t+1)+3m. \end{aligned}\]
The weight of vertices \((x_p,0)\), \((x_p,t)\) where \(1\leq p \leq m\) and vertices \((y_q,0)\), \((y_q,t)\) where \(1\leq q \leq n\) are \[\begin{aligned} w(x_p,0)&=\sum_{i=1}^nf(y_i,0)+\sum_{i=1}^nf(y_i,1)\\ &=\sum_{i=1}^n\big(b_{i,1}+m(t+1)+1\big)+ \sum_{i=1}^n\big(b_{i,2}+m(t+1)+1\big)\\ &=(n^2+2mn)(t+1)+3n,\\ w(x_p,t)&=\sum_{i=1}^n f(y_i,t-1)+f(u)\\ &=\sum_{i=1}^n\big(b_{i,t}+m(t+1)+1\big)+1\\ &=\frac{n\big(n(t+1)+1\big)}{2}+mn(t+1)+n+1\\ &=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}+1,\\ w(y_q,0)&=\sum_{i=1}^mf(x_i,0)+\sum_{i=1}^nf(x_i,1)\\ &=\sum_{i=1}^m(a_{i,1}+1)+\sum_{i=1}^m(a_{i,2}+1)\\ &=m^2(t+1)+3m,\\ w(y_q,t)&=\sum_{i=1}^mf(x_i,t-1)+f(u)\\ &=\sum_{i=1}^m\big(a_{i,t}+1\big)+1\\ &=\frac{m\big(m(t+1)+1\big)}{2}+m+1\\ &=\frac{m^2(t+1)}{2}+\frac{3m}{2}+1. \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{i=1}^m f(x_i,t)+\sum_{i=1}^nf(y_i,t)\\ &=\sum_{i=1}^n(a_{i,t+1}+1)+\sum_{i=1}^n\big(b_{i,t+1}+m(t+1)+1\big)\\ &=\frac{m\big(m(t+1)+1\big)}{2}+m+\frac{n\big(n(t+1)+1\big)}{2}+mn(t+1)+n\\ &=\frac{(m+n)^2(t+1)}{2}+\frac{3(m+n)}{2}. \end{aligned}\]
As the weight of vertices are the same as those obtained in Case 1, \(f\) is a local distance antimagic labeling of \(H\) that assigns five distinct weights to its vertices.
Case 3. \(t,n\) both even and \(m\) odd.
As \((t+1)\equiv m\ (\bmod\ 2)\), by Theorem 1.1 there exists a magic rectangle \(A=(a_{i,j})\) having \(m\) rows and \((t+1)\) columns with row sum\(=\frac{(t+1)(m(t+1)+1)}{2}\) and column sum\(=\frac{m(m(t+1)+1)}{2}\). We use this magic rectangle to label \(H\). Define a bijection \(f\colon V(H)\rightarrow\{1,2,\dots, (m+n)(t+1), (m+n)(t+1)+1\}\) by \(f(u)=1\), and for \(0\leq j \leq t\), \[\begin{aligned} f(x_i,j)&=a_{i,j+1}+1 \hspace{0.5 in} \text{for $i=1,2,\dots,m$, }\\ f(y_i,j)&=\begin{cases} m(t+1)+1+(i-1)(t+1)+j &\text{for $i=1,3,\dots,n-1$,}\\ m(t+1)+i(t+1)+2-j &\text{for $i=2,4,\dots,n$.} \end{cases} \end{aligned}\]
As seen in Case 1, for any fixed \(j\in \{0,1,2,\dots,t\}\), we have \[\begin{aligned} \sum_{i=1}^n f(y_i,j)&=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2} \quad \text{and}\\ \sum_{i=1}^nf(x_i,j)&=\sum_{i=1}^m(a_{i,j+1}+1)=\frac{m\big(m(t+1)+1\big)}{2}+m=\frac{m^2(t+1)}{2}+\frac{3m}{2}. \end{aligned}\]
For the weight of vertices \((x_p,j)\), where \(1\leq p \leq m\) and \(1\leq j \leq t-1\) and vertices \((y_q,j)\), where \(1\leq q \leq n\) and \(1\leq j \leq t-1\), we obtain \[\begin{aligned} w(x_i,j)&=\sum_{i=1}^n f(y_i,j-1)+\sum_{i=1}^nf(y_i,j+1)=2\bigg[ \frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\bigg]\\ &=(n^2+2mn)(t+1)+3n,\\ w(y_i,j)&=\sum_{i=1}^m f(x_i,j-1)+\sum_{i=1}^mf(x_i,j+1)=2\bigg[\frac{m^2(t+1)}{2}+\frac{3m}{2}\bigg]\\ &=m^2(t+1)+3m. \end{aligned}\]
The weight of vertices \((x_p,0)\), \((x_p,t)\) where \(1\leq p \leq m\) and vertices \((y_q,0)\), \((y_q,t)\) where \(1\leq q \leq n\) are \[\begin{aligned} `w(x_p,0)&=\sum_{i=1}^nf(y_i,0)+\sum_{i=1}^nf(y_i,1)=2\bigg[ \frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\bigg]\\ &=(n^2+2mn)(t+1)+3n,\\ w(x_p,t)&=\sum_{i=1}^n f(y_i,t-1)+f(u)=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}+1 ,\\ w(y_q,0)&=\sum_{i=1}^nf(x_i,0)+\sum_{i=1}^nf(x_i,1)=2\bigg[ \frac{m^2(t+1)}{2}+\frac{3m}{2}\bigg]=m^2(t+1)+3m,\\ w(y_q,t)&=\sum_{i=1}^mf(x_i,t-1)+f(u)=\frac{m^2(t+1)}{2}+\frac{3m}{2}+1. \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} w(u)&=\sum_{i=1}^m f(x_i,t)+\sum_{i=1}^nf(y_i,t)=\frac{m^2(t+1)}{2}+\frac{3m}{2}+\frac{\big(n^2+2mn\big)(t+1)}{2}+\frac{3n}{2}\\ &=\frac{(m+n)^2(t+1)}{2}+\frac{3(m+n)}{2}. \end{aligned}\]
As the weights of vertices are the same as those obtained in Case 1, \(f\) is a local distance antimagic labeling of \(H\) that assigns five distinct weights to its vertices.
Case 4. \(t\), \(m\), \(n\) are all odd.
As \((t+1)\) is even and \(m\) is odd, from Theorem 1.3 and Theorem 1.4 there exists a nearly magic rectangle \(A=(a_{i,j})\) having \(m\) rows and \((t+1)\) columns with first \(\big(\frac{t+1}{2}\big)\) column sums as \(\frac{m(m(t+1)+1)-1}{2}\) and remaining \((\frac{t+1}{2})\) column sums as \(\frac{m(m(t+1)+1)+1}{2}\). The row sums of \(A\) are equal to \(\frac{(t+1)(m(t+1)+1)}{2}\). Similarly, as \(n\) is odd, there exists a nearly magic rectangle \(B=(b_{i,j})\) having \(n\) rows and \((t+1)\) columns with the first \(\big(\frac{t+1}{2}\big)\) column sums as \(\frac{n(n(t+1)+1)-1}{2}\) and the remaining \(\big(\frac{t+1}{2}\big)\) column sums as \(\frac{n(n(t+1)+1)+1}{2}\). The row sums of \(A\) will be equal to \(\frac{(t+1)(n(t+1)+1)}{2}\). We use nearly magic rectangles \(A\) and \(B\) to label the vertices of \(H\). Define \(f\colon V(H)\rightarrow\{1,2,\dots,(m+n)(t+1), (m+n)(t+1)+1\}\) by \(f(u)=1\), and for \(0\leq j \leq t\), \[\begin{aligned} f(x_i,j)&= \begin{cases} a_{i,1}+1 &\text{for $j=0$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{t+j+2}{2}\big)}+1 &\text{for $j\equiv 1\ (\bmod\ 4)$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{t+j+3}{2}\big)}+1 &\text{for $j\equiv 2\ (\bmod\ 4)$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{j+1}{2}\big)}+1&\text{for $j\equiv 3\ (\bmod\ 4)$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{j}{2}+1\big)}+1&\text{for $j\equiv 0\ (\bmod\ 4)$, $j>0$ and $i=1,2,\dots,m,$}\\ \end{cases}\\` f(y_i,j)&= \begin{cases} b_{i,1}+m(t+1)+1 &\text{for $j=0$ and $i=1,2,\dots,n$,}\\ b_{i,\big(\frac{t+j+2}{2}\big)} +m(t+1)+1&\text{for $j\equiv 1\ (\bmod\ 4)$ and $i=1,2,\dots,n$,}\\ b_{i,\big(\frac{t+j+3}{2}\big)} +m(t+1)+1&\text{for $j\equiv 2\ (\bmod\ 4)$ and $i=1,2,\dots,n$,}\\ b_{i,\big(\frac{j+1}{2}\big)}+m(t+1)+1&\text{for $j\equiv 3\ (\bmod\ 4)$ and $i=1,2,\dots,n$,}\\ b_{i,\big(\frac{j}{2}+1\big)}+m(t+1)+1&\text{for $j\equiv 0\ (\bmod\ 4)$, $j>0$ and $i=1,2,\dots,n$.} \end{cases} \end{aligned}\]
For the weight of vertices \((x_p,j)\), where \(1\leq p \leq m\) and \(1\leq j \leq t-1\) and vertices \((y_q,j)\), where \(1\leq q \leq n\) and \(1\leq j \leq t-1\), we obtain \[\begin{aligned} &w(x_p,j)=\sum_{i=1}^n f(y_i,j-1)+\sum_{i=1}^nf(y_i,j+1)\\ &\,\,= \begin{cases} \displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{j+1}{2}\big)}+m(t+1)+1\big)+\displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{t+j+4}{2}\big)}+m(t+1)+1\big) &\text{for $j\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \sum_{i=1}^n\big(b_{i,\big(\frac{t+j+1}{2}\big)}+m(t+1)+1\big)+\displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{j+2}{2}\big)}+m(t+1)+1\big) &\text{for $j\equiv 2\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{t+j+2}{2}\big)}+m(t+1)+1\big)+\displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{j+3}{2}\big)}+m(t+1)+1\big) &\text{for $j\equiv 3\ (\bmod\ 4)$,}\\ \displaystyle \sum_{i=1}^n\big(b_{i,\big(\frac{j}{2}\big)}+m(t+1)+1\big)+\displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{t+j+3}{2}\big)}+m(t+1)+1\big) &\text{for $j\equiv 0\ (\bmod\ 4)$,} \end{cases}\\ &\,\,=\big(2mn(t+1)+2n\big)+\frac{n\big(n(t+1)+1\big)-1}{2}+\frac{n\big(n(t+1)+1\big)+1}{2}\\ &\,\,=\big(n^2+2mn\big)(t+1)+3n, \end{aligned}\] \[\begin{aligned} w(y_q,j)&=\sum_{i=1}^m f(x_i,j-1)+\sum_{i=1}^mf(x_i,j+1)\\ &= \begin{cases} \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+1}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+4}{2}\big)}+1\big) &\text{for $j\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+1}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+2}{2}\big)}+1\big) &\text{for $j\equiv 2\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+2}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+3}{2}\big)}+1\big) &\text{for $j\equiv 3\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^n\big(a_{i,\big(\frac{t+j+3}{2}\big)}+1\big) &\text{for $j\equiv 0\ (\bmod\ 4)$,} \end{cases}\\ &=\frac{m\big(m(t+1)+1\big)-1}{2}+m+\frac{m\big(m(t+1)+1\big)+1}{2}+m\\ &=m^2(t+1)+3m. \end{aligned}\]
The weight of vertices \((x_p,0)\), \((x_p,t)\) where \(1\leq p \leq m\) and vertices \((y_q,0)\), \((y_q,t)\) where \(1\leq q \leq n\) are \[\begin{aligned} w(x_p,0)&=\sum_{i=1}^n f(y_i,0)+\sum_{i=1}^nf(y_i,1)\\ &=\sum_{i=1}^n \big(b_{i,1}+m(t+1)+1\big)+\sum_{i=1}^n\big(b_{i,\big(\frac{t+3}{2}\big)}+m(t+1)+1\big)\\ &=\big(2mn(t+1)+2n\big)+\frac{n\big(n(t+1)+1\big)-1}{2}+\frac{n\big(n(t+1)+1\big)+1}{2}\\ &=\big(n^2+2mn\big)(t+1)+3n,\\ w(x_p,t)&=\sum_{i=1}^nf(y_i,t-1)+f(u)\\ &=\begin{cases} \displaystyle\sum_{i=1}^n\big(b_{i,\big(\frac{t+1}{2}\big)}+m(t+1)+1\big)+1&\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^n\big(b_{i,t+1}+m(t+1)+1\big)+1 &\text{for $t\equiv 3\ (\bmod\ 4)$,} \end{cases}\\ &=\begin{cases} \displaystyle\frac{n\big(n(t+1)+1\big)-1}{2}+mn(t+1)+n+1 &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\frac{n\big(n(t+1)+1\big)+1}{2}+mn(t+1)+n+1 &\text{for $t\equiv 3\ (\bmod\ 4)$,} \end{cases}\\ &=\begin{cases} \displaystyle \frac{(n^2+2mn)(t+1)}{2}+\frac{3n+1}{2} &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \frac{(n^2+2mn)(t+1)}{2}+\frac{3n+3}{2} &\text{for $t\equiv 3\ (\bmod\ 4)$,} \end{cases}\\ w(y_p,0)&=\sum_{i=1}^m f(x_i,0)+\sum_{i=1}^mf(x_i,1)\\ &=\sum_{i=1}^m \big(a_{i,1}+1\big)+\sum_{i=1}^n\big(a_{i,\big(\frac{t+3}{2}\big)}+1\big)\\ &=\frac{m\big(m(t+1)+1)-1}{2}+m+\frac{m\big(m(t+1)+1)+1}{2}+m\\ &=m^2(t+1)+3m,\\ w(y_p,t)&=\sum_{i=1}^mf(x_i,t-1)+f(u)=\begin{cases} \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+1}{2}\big)}+1\big)+1 &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \sum_{i=1}^m\big(a_{i,t+1}+1\big)+1 &\text{for $t\equiv 3\ (\bmod\ 4)$,} \end{cases}\\ &=\begin{cases} \displaystyle \frac{m\big(m(t+1)+1\big)-1}{2}+m+1 &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\frac{m\big(m(t+1)+1\big)+1}{2}+m+1 &\text{for $t\equiv 3\ (\bmod\ 4)$,}\\ \end{cases}\\ &=\begin{cases} \displaystyle\frac{m^2(t+1)}{2}+\frac{3m+1}{2} &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \frac{m^2(t+1)}{2}+\frac{3m+3}{2}&\text{for $t\equiv 3\ (\bmod\ 4)$.} \end{cases} \end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned} &w(u)=\sum_{i=1}^mf(x_i,t)+\sum_{i=1}^nf(y_i,t)\\ &=\begin{cases} \displaystyle\sum_{i=1}^m \big(a_{i,t+1}+1\big)+\sum_{i=1}^n\big(b_{i,t+1}+m(t+1)+1\big) &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m \big(a_{i,\big(\frac{t+1}{2}\big)}+1\big)+\sum_{i=1}^n\big(b_{i, \big(\frac{t+1}{2}\big)}+m(t+1)+1\big) &\text{for $t\equiv 3\ (\bmod\ 4)$,} \end{cases}\\ &=\begin{cases} \displaystyle\frac{m^2(t+1)+m+1}{2}+m+\frac{n^2(t+1)+n+1}{2}+mn(t+1)+n &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \frac{m^2(t+1)+m-1}{2}+m+\frac{n^2(t+1)+n-1}{2}+mn(t+1)+n &\text{for $t\equiv 3\ (\bmod\ 4)$,}\\ \end{cases}\\ &=\begin{cases} \displaystyle \frac{(n+m)^2(t+1)}{2}+\frac{3(n+m)}{2}+1 &\text{for $t\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle \frac{(n+m)^2(t+1)}{2}+\frac{3(n+m)}{2}-1 &\text{for $t\equiv 3\ (\bmod\ 4)$.} \end{cases} \end{aligned}\]
Note that for \(1\leq p \leq m\) and \(1\leq q \leq n\), \(w(x_p,0)>w(y_q,0)\). Also, \(w(x_p,j)>w(y_q,j-1)\), \(w(x_p,j)>w(y_q,j+1)\), \(w(y_q,j)<w(x_p,j-1)\) and \(w(y_q,j)<w(x_p,j+1)\) for \(1\leq j \leq t-2\). Further, \(w(x_p,t-1)\not=w(y_q,t)\) and \(w(x_p,t)\not=w(y_q,t-1)\). Clearly \(w(u)>w(x_p,t)>w(y_q,t)\). Therefore, adjacent vertices of \(H\) have different weights, and therefore, \(f\) is a local distance antimagic labeling of \(H\) that assigns five distinct weights to its vertices.
Case 5. \(t,m\) odd and \(n\) even.
As \((t+1)\) is even and \(m\) is odd, by Theorem 1.3 and Theorem 1.4 there exists a nearly magic rectangle \(A=(a_{i,j})\) having \((t+1)\) columns and \(m\) rows with the first \(\big(\frac{t+1}{2}\big)\) column sums as \(\frac{m\big(m(t+1)+1\big)-1}{2}\) and the remaining \(\big(\frac{t+1}{2}\big)\) column sums as \(\frac{m\big(m(t+1)+1\big)+1}{2}\). The row sums of \(A\) are equal to \(\frac{(t+1)\big(m(t+1)+1\big)}{2}\). We use this magic rectangle to label the vertices of \(H\). Define \(f\colon V(H)\rightarrow\{1,2,\dots, (m+n)(t+1),(m+n)(t+1)+1\}\) by \(f(u)=1\), and for \(0\leq j \leq t\), \[\begin{aligned} f(x_i,j)&= \begin{cases} a_{i,1}+1 &\text{for $j=0$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{t+j+2}{2}\big)}+1 &\text{for $j\equiv 1\ (\bmod\ 4)$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{t+j+3}{2}\big)}+1 &\text{for $j\equiv 2\ (\bmod\ 4)$ and $i=1,2,\dots,m$,}\\ a_{i,\big(\frac{j+1}{2}\big)}+1&\text{for $j\equiv 3\ (\bmod\ 4)$ and $i=1,2,\dots,m,$}\\ a_{i,\big(\frac{j}{2}+1\big)}+1&\text{for $j\equiv 0\ (\bmod\ 4)$, $j>0$ and $i=1,2,\dots,m$,} \end{cases}\\ f(y_i,j)&= \begin{cases} m(t+1)+(i-1)(t+1)+1+j &\text{if $i=1,3,5,\dots,n-1$,}\\ m(t+1)+i(t+1)+2-j &\text{for $i=2,4,6,\dots,n.$ } \end{cases} \end{aligned}\]
As seen in Case 1, for any fixed \(j\in \{0,1,2,\dots,t\}\), we have,\[\displaystyle \sum_{i=1}^n f(y_i,j)=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}.\]
For the weight of vertices \((x_p,j)\), where \(1\leq p \leq m\) and \(1\leq j \leq t-1\) and vertices \((y_q,j)\), where \(1\leq q \leq n\) and \(1\leq j \leq t-1\), we obtain \[\begin{aligned} w(x_p,j)&=\sum_{i=1}^nf(y_i,j-1)+\sum_{i=1}^nf(y_i,j+1)\\ &=2\bigg[\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\bigg]\\ &=(n^2+2mn)(t+1)+3n,\\ w(y_q,j)&=\sum_{i=1}^m f(x_i,j-1)+\sum_{i=1}^mf(x_i,j+1)\\ &= \begin{cases} \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+1}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+4}{2}\big)}+1\big) &\text{for $j\equiv 1\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+1}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+2}{2}\big)}+1\big) &\text{for $j\equiv 2\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{t+j+2}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j+3}{2}\big)}+1\big) &\text{for $j\equiv 3\ (\bmod\ 4)$,}\\ \displaystyle\sum_{i=1}^m\big(a_{i,\big(\frac{j}{2}\big)}+1\big)+\displaystyle\sum_{i=1}^n\big(a_{i,\big(\frac{t+j+3}{2}\big)}+1\big) &\text{for $j\equiv 0\ (\bmod\ 4)$,} \end{cases}\\ &=\frac{m\big(m(t+1)+1\big)-1}{2}+m+\frac{m\big(m(t+1)+1\big)+1}{2}+m\\ &=m^2(t+1)+3m. \end{aligned}\]
The weight of vertices \((x_p,0)\),
\((x_p,t)\) where \(1\leq p \leq m\) and vertices \((y_q,0)\), \((y_q,t)\) where \(1\leq q \leq n\) are \[\begin{aligned}
w(x_{p},0)&=\sum_{i=1}^nf(y_i,0)+\sum_{i=1}^nf(y_i,1)\\
&=2\bigg[\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}\bigg]\\
&=(n^2+2mn)(t+1)+3n,\\
w(x_p,t)&=\sum_{i=1}^nf(y,t-1)+f(u)\\
&=\frac{(n^2+2mn)(t+1)}{2}+\frac{3n}{2}+1,\\
w(y_q,0)&=\sum_{i=1}^m
f(x_i,0)+\sum_{i=1}^mf(x_i,1)\\
&=\sum_{i=1}^m
\big(a_{i,1}+1\big)+\sum_{i=1}^n\big(a_{i,\big(\frac{t+3}{2}\big)}+1\big)\\
&=\frac{m\big(m(t+1)+1)-1}{2}+m+\frac{m\big(m(t+1)+1)+1}{2}+m\\
&=m^2(t+1)+3m,\\
w(y_q,t)&=\sum_{i=1}^mf(x_i,t-1)+f(u)\\
&=\begin{cases}\displaystyle
\sum_{i=1}^m\big(a_{i,\big(\frac{t+1}{2}\big)}+1\big)+1
&\text{if $t\equiv 1\ (\bmod\ 4)$,}\\
\displaystyle \sum_{i=1}^m\big(a_{i,t+1}+1\big)+1
&\text{if $t\equiv 3\ (\bmod\ 4)$,}
\end{cases}\\
&=\begin{cases}
\displaystyle\frac{m\big(m(t+1)+1\big)-1}{2}+m+1
&\text{if $t\equiv 1\ (\bmod\ 4)$,}\\
\displaystyle\frac{m\big(m(t+1)+1\big)+1}{2}+m+1
&\text{if $t\equiv 3\ (\bmod\ 4)$,}
\end{cases}\\
&=\begin{cases}
\displaystyle\frac{m^2(t+1)}{2}+\frac{3m+1}{2}
&\text{if $t\equiv 1\ (\bmod\ 4)$,}\\
\displaystyle \frac{m^2(t+1)}{2}+\frac{3m+3}{2}
&\text{if $t\equiv 3\ (\bmod\ 4)$.}
\end{cases}
\end{aligned}\]
The weight of vertex \(u\) is \[\begin{aligned}
w(u)&=\sum_{i=1}^mf(x_i,t)+\sum_{i=1}^nf(y_i,t)\\
&=\begin{cases}
\displaystyle\sum_{i=1}^m\big(a_{i,t+1}+1\big)+\frac{(2mn+n^2)(t+1)}{2}+\frac{3n}{2}
&\text{if $t\equiv 1\ (\bmod\ 4)$,}\\
\displaystyle \sum_{i=1}^m\big(a_{i,\big(\frac{t+1}{2}\big)}+1\big)+\frac{(2mn+n^2)(t+1)}{2}+\frac{3n}{2}
&\text{if $t\equiv 3\ (\bmod\ 4)$,}
\end{cases}\\
&=\begin{cases}
\displaystyle\frac{(m+n)^2(t+1)}{2}+\frac{3n+3m+1}{2}
&\text{if $t\equiv 1\ (\bmod\ 4)$,}\\
\displaystyle\frac{(m+n)^2(t+1)}{2}+\frac{3n+3m+1}{2}
&\text{if $t\equiv 3\ (\bmod\ 4)$.}
\end{cases}
\end{aligned}\]
Note that for \(1\leq p \leq m\) and \(1\leq q \leq n\), \(w(x_p,0)>w(y_q,0)\). Also, \(w(x_p,j)>w(y_q,j-1)\), \(w(x_p,j)>w(y_q,j+1)\), \(w(y_q,j)<w(x_p,j-1)\) and \(w(y_q,j)<w(x_p,j+1)\) for \(1\leq j \leq t-2\). Further, \(w(x_p,t-1)\not=w(y_q,t)\) and \(w(x_p,t)\not=w(y_q,t-1)\). Clearly \(w(u)>w(x_p,t)>w(y_q,t)\). Therefore, adjacent vertices of \(H\) have different weights, and therefore, \(f\) is a local distance antimagic labeling of \(H\) that assigns five distinct weights to its vertices.
The lower bound follows from the fact that \(\chi(\mu_t(K_{m,n}))=\chi(K_{m,n})+1=3\) and that \(\chi(\mu_t(K_{m,n}))\leq\chi_{ld}(\mu_t(K_{m,n})).\) ◻
In this article, we studied the local distance antimagic labeling of the Mycielskian construction and the Generalized Mycielskian construction of regular graphs and complete bipartite graphs. We also obtained an upper bound on local distance antimagic chromatic number of such graphs.
The following problems naturally arise.
Problem 3.1. Obtain the exact values of the local distance antimagic chromatic number of the Mycielskian and the Generalized Mycielskian of regular graphs.
Problem 3.2. Obtain the bounds or the exact values ofthe local distance antimagic chromatic number of the Mycielskian and the Generalized Mycielskian of non-regular graphs.
Problem 3.3. Obtain the bounds or the exact values of local distance antimagic chromatic number of the Mycielskian and the Generalized Mycielskian of trees of order \(n\) having \(k\) leaves.
