A graph \(G=(V,E)\) is said to be an absolute mean graceful graph if there exists a one-to-one function \(f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm|E(G)|\}\) such that the induced edge-labeling function \(f^*:E(G)\to \{1,2,\ldots,|E(G)|\}\), defined by \[f^*(xy)=\left\lceil{\dfrac{|f(x)-f(y)|}{2}}\right\rceil,\] is bijective. The labeling function \(f\) is called an absolute mean graceful labeling of the graph \(G\). In this paper, we obtain absolute mean graceful labelings for \(m\)-splitting and \(m\)-shadow graphs of various graphs.
By \(G=(V,E)\), we mean a simple, finite, connected, and undirected graph, where \(V\) is the set of vertices of \(G\) and \(E\) is the set of edges of \(G\). For all terminology and notation related to graph theory, we follow Harary [10].
A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. For various results and references related to graph labeling, we follow Gallian [8]. In 1967, Rosa [17] introduced the concepts of \(\beta\)-valuation and \(\alpha\)-valuation in graph labeling. The \(\beta\)-valuation was later known as graceful labeling due to Golomb [9]. Some applications related to graph labeling can be found in [5, 6, 15, 16].
Absolute mean graceful labeling was introduced by Kaneria and Chudasama [11]. They defined absolute mean graceful labeling for the path \(P_n\), cycle \(C_n\), complete bipartite graph \(K_{m,n}\), grid graph \(P_m \times P_n\), step grid graph \(St_n\), and double step grid graph \(DSt_n\). In [7], the same authors also obtained absolute mean graceful labeling for some graphs created by duplication. Kaneria et al. [12] proved that path unions of graphs such as trees, paths \(P_n\), cycles \(C_n\), complete bipartite graphs \(K_{m,n}\), grid graphs \(P_m \times P_n\), step grid graphs \(St_n\), and double step grid graphs \(DSt_n\) are absolute mean graceful graphs. Akbari et al. [2, 3] obtained absolute mean graceful labeling for the jewel graph, jellyfish graph, and barycentric subdivision of various graphs. Akbari et al. [4] investigated absolute mean graceful labeling for the disjoint union of various graphs. Kaneria and Shah [13, 14] defined absolute mean graceful labeling for graphs, the \(m\)-splitting graph of a path and a star, the splitting graph of a bistar, the degree splitting graph of some graphs, and some cycle-related graphs.
In this paper, we investigate absolute mean graceful labeling for some \(m\)-splitting and \(m\)-shadow-related graphs. We now recall some definitions that are useful for this paper.
Definition 1.1([11]).A function \(f\) is said to be an absolute mean graceful labeling of a graph \(G\) with \(q\) edges if \(f\) is a one-to-one function from \(V(G)\) to the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\) such that, when each edge \(uv\) of \(G\) is assigned the label \[f^*(uv)=\left\lceil \dfrac{|f(u)-f(v)|}{2} \right\rceil,\] the set of resulting edge labels is \(\{1,2,3,\ldots,q\}\). Here, \(\lceil \ \rceil\) denotes the ceiling function, which maps any real number \(x\) to the smallest integer greater than or equal to \(x\). A graph \(G\) that admits an absolute mean graceful labeling is called an absolute mean graceful graph.
Definition 1.2([8]).Let \(G\) be a graph. For each vertex \(v_i\) of \(G\), take a new vertex \(v_i'\). Join \(v_i'\) to those vertices of \(G\) that are adjacent to \(v_i\). The graph thus obtained is called the splitting graph of \(G\), and it is denoted by \(S'(G)\).
Definition 1.3([8]).The shadow graph \(D_2(G)\) of a connected graph \(G\) is constructed by taking two copies, \(G_1\) and \(G_2\), of \(G\) and joining each vertex \(u\) of \(G_1\) to the neighbours of the corresponding vertex \(v\) in \(G_2\).
Definition 1.4([1]).Let \(G\) be a graph. For each vertex \(v\) of \(G\), take new \(m\) vertices \(v^1,v^2,\ldots,v^m\). Join \(v^i\) to those vertices of \(G\) that are adjacent to \(v\) in \(G\). The graph thus obtained is called the \(m\)-splitting graph of \(G\), and it is denoted by \(Spl_m(G)\).
If \(G\) has \(p\) vertices and \(q\) edges, then the graph \(Spl_m(G)\) has \((m+1)p\) vertices and \((2m+1)q\) edges.
Definition 1.5([1]).The \(m\)-shadow graph \(D_m(G)\) of a connected graph \(G\) is constructed by taking \(m\) copies \(G_1,G_2,\ldots,G_m\) of \(G\) and joining each vertex \(u\) in \(G_i\) to the neighbours of the corresponding vertex \(v\) in \(G_j\), for \(1 \leq i,j \leq m\).
If \(G\) has \(p\) vertices and \(q\) edges, then the graph \(D_m(G)\) has \(mp\) vertices and \(m^2q\) edges.
From the above definitions, the \(1\)-splitting graph is the splitting graph, and the \(2\)-shadow graph is the shadow graph of a given graph \(G\).
Definition 1.6. The bistar \(B_{m,n}\) is the graph obtained by joining the center vertices of two stars \(K_{1,m}\) and \(K_{1,n}\) by an edge.
Theorem 2.1. The \(m\)-splitting graph of the complete bipartite graph, \(Spl_m(K_{r,t})\), is an absolute mean graceful graph for all \(m,r,t\geq1\).
Proof. Consider the complete bipartite graph \(K_{r,t}\) with vertices \[v_1,v_2,\ldots,v_r,u_1,u_2,\ldots,u_t.\] Let \(v_i^j\) and \(u_i^j\) be the vertices corresponding to the vertices \(v_i\) and \(u_i\), respectively, for \(j=1,2,\ldots,m\). Let \(G\) be the graph \(Spl_m(K_{r,t})\). Then \[p=|V(G)|=(m+1)(r+t)\] and \[q=|E(G)|=(2m+1)rt.\]
Now, consider the labeling function \[f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm q\}\] defined as follows: \[\begin{array}{lll} f(v_i)=q-2t(m+1)(i-1), & \text{for } i=1,2,\ldots,r, \\[4pt] f(v_i^j)=f(v_i)-2mt(r-i)-2rtj, & \text{for } i=1,2,\ldots,r \text{ and } j=1,2,\ldots,m, \\[4pt] f(u_i)=-q+2(mt+i-1), & \text{for } i=1,2,\ldots,t, \\[4pt] f(u_i^j)=f(u_i)-2tj, & \text{for } i=1,2,\ldots,t \text{ and } j=1,2,\ldots,m. \end{array}\]
The above-defined function \(f\) assigns distinct labels to every vertex of the graph \(G\) from the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\); hence, \(f\) is one-to-one. Now consider the induced edge-labeling function \(f^*\) defined by \[f^*(xy)=\left\lceil \dfrac{|f(x)-f(y)|}{2}\right\rceil\] for every edge \(xy\in E(G)\). Then, \[f^*(\{v_i^ju_t,v_i^ju_{t-1},\ldots,v_i^ju_1:1\leq i\leq r,\ 1\leq j\leq m\}) =\{1,2,\ldots,mrt\},\] \[f^*(\{v_ru_t,v_ru_{t-1},\ldots,v_ru_1\}) =\{mrt+1,mrt+2,\ldots,mrt+t\},\] \[f^*(\{v_ru_i^j,v_ru_i^j,\ldots,v_ru_i^j:1\leq i\leq r,\ 1\leq j\leq m\}) =\{mrt+t+1,mrt+t+2,\ldots,mrt+t+mt\},\] \[f^*(\{v_{r-1}u_t,v_{r-1}u_{t-1},\ldots,v_{r-1}u_1\}) =\{mrt+t+mt+1,mrt+t+mt+2,\ldots,mrt+2t+mt\},\] \[\begin{aligned} f^*&(\{v_{r-1}u_i^j,v_{r-1}u_i^j,\ldots,v_{r-1}u_i^j:1\leq i\leq r,\ 1\leq j\leq m\})\\ &=\{mrt+2t+mt+1,mrt+2t+mt+2,\ldots,mrt+2t+2mt\}, \end{aligned}\] \[\vdots\] \[\begin{aligned} f^*&(\{v_1u_t,v_1u_{t-1},\ldots,v_1u_1\})=\{mrt+(r-1)t+(r-1)mt+1,\\ &mrt+(r-1)t+(r-1)mt+2,\ldots,mrt+rt+(r-1)mt\}, \end{aligned}\] \[\begin{aligned} f^*&(\{v_1u_i^j,v_1u_i^j,\ldots,v_1u_i^j:1\leq i\leq r,\ 1\leq j\leq m\})\\ &=\{mrt+rt+(r-1)mt+1,mrt+rt+(r-1)mt+2,\ldots,mrt+rt+rmt=q\}. \end{aligned}\]
Thus, \[f^*(E(G))=\{1,2,\ldots,q\},\] where \(|E(G)|=q\). Therefore, \(f^*\) is bijective. Hence, the function \(f\) is an absolute mean graceful labeling of the graph \(Spl_m(K_{r,t})\) for all \(m,r,t\geq1\). ◻
Illustration 2.2. An absolute mean graceful labeling of the graph \(Spl_2(K_{2,3})\) is shown in Figure 1.
Theorem 2.3. The \(m\)-splitting graph of the even cycle, \(Spl_m(C_{2k})\), is an absolute mean graceful graph for all \(m\geq1\) and \(k\geq2\).
Proof. Consider the even cycle \(C_{2k}\) with vertices \(v_1,v_2,\ldots,v_{2k}\). Let \(v_i^j\) be the vertices corresponding to each vertex \(v_i\) of the graph \(C_{2k}\), for \(j=1,2,\ldots,m\). Let \(G\) be the graph \(Spl_m(C_{2k})\). Then \[p=|V(G)|=2k(m+1)\] and \[q=|E(G)|=2k(2m+1).\]
Now, consider the labeling function \[f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm q\}\] defined as follows: \[f(v_i)= \begin{cases} (-1)^{i+1}\bigl(q-2(i-1)\bigr), & \text{for } i=1,2,\ldots,k+1,\\[4pt] (-1)^{i+1}\bigl(q-1-2(2k-i)\bigr), & \text{for } i=k+2,k+3,\ldots,2k, \end{cases}\] and \[f(v_i^j)= \begin{cases} f(v_i)-4kj, & \text{for } i=1,3,5,\ldots,2k-1,\\[4pt] f(v_i)+4(m+1)k+4k(j-1), & \text{for } i=2,4,6,\ldots,2k, \end{cases}\] for all \(j=1,2,\ldots,m\).
The above-defined function \(f\) assigns distinct labels to every vertex of the graph \(G\) from the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\); hence, \(f\) is one-to-one. Now consider the induced edge-labeling function \(f^*\) defined by \[f^*(xy)=\left\lceil\dfrac{|f(x)-f(y)|}{2}\right\rceil\] for every edge \(xy\in E(G)\). Then \(f^*\) assigns distinct labels to every edge of the graph \(G\) from the set \(\{1,2,\ldots,q\}\) as follows: \[f^*(v_kv_{k+1}^m)=1,\quad f^*(v_{k+2}v_{k+1}^m)=2,\quad f^*(v_kv_{k-1}^m)=3,\quad f^*(v_{k+1}v_{k+2}^m)=4,\quad \ldots,\] \[f^*(v_1v_2^m)=2k-1,\quad f^*(v_1v_{2k}^m)=2k,\quad f^*(v_{k+1}v_{k+2}^{m-1})=2k+1,\quad \ldots,\] \[f^*(v_1v_{2k}^{m-1})=4k,\quad \ldots,\quad f^*(v_1v_2)=q-1,\quad f^*(v_1v_{2k})=q.\]
Thus, \(f^*\) is bijective. Therefore, the function \(f\) is an absolute mean graceful labeling of the graph \(Spl_m(C_{2k})\) for all \(m\geq1\) and \(k\geq2\). ◻
Illustration 2.4. An absolute mean graceful labeling of the graph \(Spl_3(C_6)\) is shown in Figure 2.
Theorem 2.5. The \(m\)-shadow graph of the even cycle, \(D_m(C_{2k})\), is an absolute mean graceful graph for all \(m\geq2\) and \(k\geq2\).
Proof. Consider \(m\) copies of the graph \(C_{2k}\). Let \[v_1^j,v_2^j,\ldots,v_{2k}^j\] be the vertices of the \(j\)th copy of the cycle \(C_{2k}\), for \(j=1,2,\ldots,m\). Let \(G\) be the graph \(D_m(C_{2k})\). Then \[p=|V(G)|=2km\] and \[q=|E(G)|=2km^2.\]
Now, consider the labeling function \[f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm q\}\] defined as follows: \[f(v_i^1)= \begin{cases} (-1)^{i+1}\bigl(q-2(i-1)\bigr), & \text{for } i=1,2,\ldots,k+1,\\[4pt] (-1)^{i+1}\bigl(q-1-2(2k-i)\bigr), & \text{for } i=k+2,k+3,\ldots,2k, \end{cases}\] and \[f(v_i^j)= \begin{cases} f(v_i^1)-4k(j-1), & \text{for } i=1,3,5,\ldots,2k-1,\\[4pt] f(v_i^1)+4km(j-1), & \text{for } i=2,4,6,\ldots,2k, \end{cases}\] for all \(j=2,3,\ldots,m\).
The above-defined function \(f\) assigns distinct labels to every vertex of the graph \(G\) from the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\); hence, \(f\) is one-to-one. Now consider the induced edge-labeling function \(f^*\) defined by \[f^*(xy)=\left\lceil\dfrac{|f(x)-f(y)|}{2}\right\rceil\] for every edge \(xy\in E(G)\). Then \(f^*\) assigns distinct labels to every edge of the graph \(G\) from the set \(\{1,2,\ldots,q\}\) as follows: \[f^*(v_{k+1}^mv_k^m)=1,\quad f^*(v_{k+1}^mv_{k+2}^m)=2,\quad f^*(v_k^mv_{k-1}^m)=3,\quad f^*(v_{k+2}^mv_{k+3}^m)=4,\quad \ldots,\] \[f^*(v_1^mv_2^m)=2k-1,\quad f^*(v_1^mv_{2k}^m)=2k,\quad f^*(v_{k+1}^mv_k^{m-1})=2k+1,\] \[f^*(v_{k+1}^mv_{k+2}^{m-1})=2k+2,\quad \ldots,\quad f^*(v_1^1v_2^1)=q-1,\quad f^*(v_1^1v_{2k}^1)=q.\]
Thus, \(f^*\) is bijective. Therefore, the function \(f\) is an absolute mean graceful labeling of the graph \(D_m(C_{2k})\) for all \(m\geq2\) and \(k\geq2\). ◻
Illustration 2.6. An absolute mean graceful labeling of the graph \(D_3(C_{10})\) is shown in Figure 3.
Theorem 2.7. The \(m\)-shadow graph of the path, \(D_m(P_n)\), is an absolute mean graceful graph for all \(m,n\geq2\).
Proof. Consider \(m\) copies of the graph \(P_n\). Let \[v_1^j,v_2^j,\ldots,v_n^j\] be the vertices of the \(j\)th copy of \(P_n\), for \(j=1,2,\ldots,m\). Let \(G\) be the graph \(D_m(P_n)\). Then \[p=|V(G)|=mn\] and \[q=|E(G)|=m^2(n-1).\]
Now, consider the labeling function \[f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm q\}\] defined as follows: \[f(v_i^j)= \begin{cases} q-i+1-2(n-1)(j-1), & \text{if } i \text{ is odd},\\[4pt] -q+i-1+2m(n-1)(j-1), & \text{if } i \text{ is even}, \end{cases}\] for all \(i=1,2,\ldots,n\) and \(j=1,2,\ldots,m\).
The above-defined function \(f\) assigns distinct labels to every vertex of the graph \(G\) from the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\); hence, \(f\) is one-to-one. Now consider the induced edge-labeling function \(f^*\) defined by \[f^*(xy)=\left\lceil\dfrac{|f(x)-f(y)|}{2}\right\rceil\] for every edge \(xy\in E(G)\). Then \(f^*\) assigns distinct labels to every edge of the graph \(G\) from the set \(\{1,2,\ldots,q\}\) as follows: \[f^*(v_n^mv_{n-1}^m)=1,\quad f^*(v_{n-1}^mv_{n-2}^m)=2,\quad f^*(v_{n-2}^mv_{n-3}^m)=3,\quad \ldots,\] \[f^*(v_2^mv_1^m)=n-1,\quad \ldots,\quad f^*(v_3^1v_2^1)=q-1,\quad f^*(v_2^1v_1^1)=q.\]
Thus, \(f^*\) is bijective. Therefore, the function \(f\) is an absolute mean graceful labeling of the graph \(D_m(P_n)\) for all \(m,n\geq2\). ◻
Illustration 2.8. An absolute mean graceful labeling of the graph \(D_4(P_7)\) is shown in Figure 4.
Theorem 2.9. The \(m\)-shadow graph of the bistar, \(D_m(B_{r,t})\), is an absolute mean graceful graph for all \(m,r,t\geq2\).
Proof. Consider the bistar graph \(B_{r,t}\) with vertex set \[\{u_0,u_1,\ldots,u_r,v_0,v_1,\ldots,v_t\}\] and edge set \[\{u_0u_1,u_0u_2,\ldots,u_0u_r,u_0v_0,v_0v_1,v_0v_2,\ldots,v_0v_t\}.\] Now consider \(m\) copies of the graph \(B_{r,t}\). Let \[u_0^j,u_1^j,u_2^j,\ldots,u_r^j,v_0^j,v_1^j,v_2^j,\ldots,v_t^j\] be the vertices of the \(j\)th copy of \(B_{r,t}\), for \(j=1,2,\ldots,m\). Let \(G\) be the graph \(D_m(B_{r,t})\). Then \[p=|V(G)|=m(r+t+2)\] and \[q=|E(G)|=m^2(r+t+1).\]
Now, consider the labeling function \[f:V(G)\to \{0,\pm1,\pm2,\ldots,\pm q\}\] defined as follows: \[\begin{array}{lll} f(u_0^j)=-q+2m(j-1)(r+t+1), & \text{for } j=1,2,\ldots,m, \\[4pt] f(u_i^j)=q-2(j-1)(r+t+1)-2(i-1), & \text{for } i=1,2,\ldots,r \text{ and } j=1,2,\ldots,m, \\[4pt] f(v_0^j)=q-2(j-1)(r+t+1)-2r, & \text{for } j=1,2,\ldots,m, \\[4pt] f(v_i^j)=-q+2m(j-1)(r+t+1)+2i, & \text{for } i=1,2,\ldots,t \text{ and } j=1,2,\ldots,m. \end{array}\]
The above-defined function \(f\) assigns distinct labels to every vertex of the graph \(G\) from the set \(\{0,\pm1,\pm2,\ldots,\pm q\}\); hence, \(f\) is one-to-one. Now consider the induced edge-labeling function \(f^*\) defined by \[f^*(xy)=\left\lceil\dfrac{|f(x)-f(y)|}{2}\right\rceil\] for every edge \(xy\in E(G)\). Then \(f^*\) assigns distinct labels to every edge of the graph \(G\) from the set \(\{1,2,\ldots,q\}\) as follows: \[f^*(v_0^mv_t^m)=1,\quad f^*(v_0^mv_{t-1}^m)=2,\quad f^*(v_0^mv_{t-2}^m)=3,\quad \ldots,\] \[f^*(v_0^mv_1^m)=t,\quad f^*(v_0^mu_0^m)=t+1,\quad f^*(u_0^mu_r^m)=t+2,\quad \ldots,\] \[f^*(u_0^1u_2^1)=q-1,\quad f^*(u_0^1u_1^1)=q.\]
Thus, \(f^*\) is bijective. Therefore, the function \(f\) is an absolute mean graceful labeling of the graph \(D_m(B_{r,t})\) for all \(m,r,t\geq2\). ◻
Illustration 2.10. An absolute mean graceful labeling of the graph \(D_3(B_{4,3})\) is shown in Figure 5.
In this paper, we investigated absolute mean graceful labeling for various \(m\)-splitting and \(m\)-shadow graphs. The illustrations help to clarify the labeling patterns obtained in the main results. In Theorems 2.3 and 2.5, we obtained absolute mean graceful labelings for the \(m\)-splitting and \(m\)-shadow graphs of even cycles, namely \(Spl_m(C_{2k})\) and \(D_m(C_{2k})\). By applying a similar pattern, we could not obtain absolute mean graceful labelings for the \(m\)-splitting and \(m\)-shadow graphs of odd cycles. Therefore, the case of odd cycles is presented as an open problem.
Does there exist an absolute mean graceful labeling for the graphs \(Spl_m(C_{2k+1})\) and \(D_m(C_{2k+1})\)?
Obtaining similar results for different graph families using various graph operations also remains an open area of research.