Contents

Cyclic-antimagic construction of ladders

Author(s): Muhammad Awais Umar1
1Government Degree College (B), Sharaqpur Shareef, Pakistan.
Copyright © Muhammad Awais Umar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A simple graph \(G=(V,E)\) admits an \(H\)-covering if every edge in the edge set \(E(G)\) belongs to at least one subgraph of \(G\) isomorphic to a given graph \(H\). A graph \(G\) having an \(H\)-covering is called \((a,d)-H\)-antimagic if the function \(h:V(G)\cup E(G) \to \{1,2,\dots, |V(G)|+|E(G)| \}\) defines a bijective map such that, for all subgraphs \(H’\) of \(G\) isomorphic to \(H\), the sums of labels of all vertices and edges belonging to \(H’\) constitute an arithmetic progression with the initial term \(a\) and the common difference \(d.\) Such a graph is named as super \((a,d)-H\)-antimagic if \(h(V(G))= \{ 1,2,3,\dots,|V(G)|\}\). For \(d=0\), the super \((a,d)-H\)-antimagic graph is called \(H\)-supermagic. In the present paper, we study the existence of super \((a,d)\)-cycle-antimagic labelings of ladder graphs for certain differences \(d\)

Keywords: Cycle-antimagic, super cycle-antimagic, super \((a,d)\)-cycle-antimagic, \(C_4\)-antimagic, ladder graph.

1. Introduction

Let \(G=(V,E)\) be a finite simple graph. A family of subgraphs \(H_1, H_2, \dots, H_t\) of the graph \(G\) with property that each element of \(E\) belongs to at least one subgraph \(H_i\), \(i=1, 2, \dots, t\), is classified as an edge-covering of \(G\). With the possibility, \(H_i\) isomorphic to a given graph \(H\), \(G\) is said to admit an \(H\)-covering.

Suppose a \((p,q)\)-graph \(G\) admits an \(H\)-covering. A bijective function \(h:V(G)\cup E(G) \to \{1,2,\dots, p+q \}\) is called a total labeling for \(G\). The associated \(H\)-weight is defined as \[wt_h(H) = \sum\limits_{v\in V(H)} h(v) + \sum\limits_{e\in E(H)} h(e).\] A total labeling \(h:V(G)\cup E(G) \to \{1,2,\dots, p+q \}\) is then called an \(H\)-magic labeling, if there exists a positive integer \(m_c\) (called the magic constant) such that for every subgraph \(H'\) of \(G\) isomorphic to \(H\), \(wt_h(H) = m_c.\) The graph \(G\) admitting such a labeling is called \(H\)-magic.

In addition, if the \(H\)-weights constitute an arithmetic progression \(a, a+d, a+2d,\dots , a+(t -1)d\), where \(a>0\) and \(d\ge 0\) are two integers, and \(t\) is the number of all subgraphs of \(G\) isomorphic to \(H\), then we say that graph \(G\) is an \((a,d)\)\(H\)-antimagic. The restriction \(h(V)= \{ 1,2,\dots,p\}\) makes \(G\) a super \((a,d)\)\(H\)-antimagic. If the subgraph \(H\) is isomorphic to a cycle \(C_k\) for some \(k\), then super \((a,d)\)\(H\)-antimagic labeling is referred to a super \((a,d)\)-cycle-antimagic labeling.

The \(H\)-supermagic labelings were first studied by Gutiérrez et al. in [1] as an extension of the edge-magic and super edge-magic labelings introduced by Kotzig et al. [2] and Enomoto et al. [3], respectively. Gutiérrez et al. considered star-supermagic and path-supermagic labelings of some connected graphs and proved that the path \(P_n\) and the cycle \(C_n\) are \(P_m\)-supermagic for some \(m\). Maryati et al. [4] gave \(P_m\)-supermagic labelings of some trees such as shrubs, subdivision of shrubs and banana tree graphs. Lladó et al. [5] investigated \(C_n\)-supermagic graphs and proved that wheels, windmills, books and prisms are \(C_m\)-magic for some \(m\). Some results on \(C_n\)-supermagic labelings of several classes of graphs can be found in [6,7]. Other examples of \(H\)-supermagic graphs with different choices of \(H\) have been given by Jeyanthi et al. in [8]. Inayah, Lladó and Moragas [9] gave a connection between graceful trees and antimagic \(H\)-decomposition of complete graphs. Maryati et al. [6] investigated the \(G\)-supermagicness of a disjoint union of \(c\) copies of a graph \(G\) and showed that disjoint union of any paths is \(cP_m\)-supermagic for some \(c\) and \(m\).

Motivated by \(H\)-(super)magic labelings, Inayah et al. [10] introduced the \((a,d)\)\(H\)-antimagic labeling. In [11] they investigated the super \((a,d)\)\(H\)-antimagic labelings for some shackles of a connected graph \(H\). In [12] Miller et al. exhibit an operation on graphs which keeps super H-antimagic properties using technique of partitioning sets of integers. The existence of super \((a,d)\)\(H\)-antimagic labelings for disconnected graphs is studied in [13] and there is proved that if a graph \(G\) admits a (super) \((a,d)\)\(H\)-antimagic labeling, where \(d=|E(H)|-|V(H)|\), then the disjoint union of \(m\) copies of the graph \(G\), denoted by \(mG\), admits a (super) \((b,d)\)\(H\)-antimagic labeling as well.

The (super) \((a,d)\)\(H\)-antimagic labeling is related to a super \(d\)-antimagic labeling of type \((1,1,0)\) of a plane graph that is the generalization of a face-magic labeling introduced by Lih [14]. Further information on super \(d\)-antimagic labelings can be found in [15,16].

For \(H\cong K_2\), (super) \((a,d)\)\(H\)-antimagic labelings are also called (super) \((a,d)\)-edge-antimagic total labelings and have been introduced in [17]. More results on \((a,d)\)-edge-antimagic total labelings, can be found in [15,18-20]. The vertex version of these labelings for generalized pyramid graphs is given in [21].

A ladder is a Cartesian product \(L_m\cong P_m\times P_2\) of the path on \(m\) vertices with the path on two vertices. The vertex set \(V(L_m)\) consists of the elements \(\{u_i, v_i: 1 \leq i \leq m\}\) and the edge set \(E(L_m)\) consists of the elements \(\{u_iv_i: 1 \leq i \leq m\} \cup \{u_iu_{i+1},v_iv_{i+1}:1\leq i \leq m-1\}.\)

In [7], Ngurah et al. proved that ladder graph \(L_n\) is \(C_4\)-supermagic for every \(n\ge 2\).

In the present paper, we will study the existence of the super cycle-antimagic labelings of ladder graphs \(L_m\). More explicitly, we will describe super \((a,d)\)\(C_4\)-antimagic labelings of ladder graphs for differences \(0\le d \le 15\).

2. Results

Let \(C_4^{(i)}\), \(1 \leq i \leq m-1\) be the subcycle of \(L_m\) with \(V(C_4^{(i)})=\{u_{i},u_{i+1},v_{i},v_{i+1}\}\)
and \(E(C_4^{(i)})=\{u_{i} u_{i+1},v_{i}v_{i+1},u_{i}v_{i}, u_{i+1}v_{i+1}\}\).
For the \(C_4\)-weight of the cycle \(C_4^{(i)}\), \(i=1,2,\dots,m-1\), under the total labeling \(h\) we get: \[\begin{aligned} wt_h(C_4^{(i)})&= h(u_{i})+h(v_{i})+h(u_{i+1})+h(v_{i+1})\\ &+ h(u_{i} u_{i+1})+h(v_{i} v_{i+1})+h(u_{i} v_{i})+h(u_{i+1} v_{i+1}). \end{aligned}\] The following theorem shows that ladder graph \(L_m\) admits super \((a,d)\)\(C_4\)-antimagic labelings for differences \(0\le d \le 6\).

Theorem 1. Let \(m \geq 3\) be a positive integer. Then the ladder \(L_m\) admits a super \((a,d)\)\(C_4\)-antimagic labeling for \(d \in \{0,1,2,3,4,5,6\}\).

Proof. Label the vertices of the ladder \(L_m\) by the following integers: \[\begin{aligned} h(u_i)&= i& \text{if }\ i=1, 2, \dots,m,\\ h(v_i)&= 2m+1-i& \text{if }\ i=1, 2, \dots,m. \end{aligned}\] Clearly, under the vertex labeling \(h\) the vertices of \(L_m\) receive labels from 1 up to \(2m\) and for partial weights of \(C_4^{(i)}\) for every \(i=1,2,\dots,m-1\) we get \[\begin{aligned} w_h= h(u_i)+h(u_{i+1}) + h(v_i)+h(v_{i+1}) = 4m+2. \label{vertex-weight} \end{aligned}\tag{1}\]

We define the labelings \(h_j\), \(j=0,1,2,\dots, 6\), for the edges of \(L_m\) in the following way:
if \(i=1,2,\dots,m-1\) then \[h_j(u_iu_{i+1})=\begin{cases} 3m-i & \text{for}\ j=0,\\ 4m-i & \text{for}\ j=1,\\ 3m+i & \text{for}\ j=2,3,4,\\ 3m-1+2i & \text{for}\ j=5,6, \end{cases}\] \[h_j(v_iv_{i+1})=\begin{cases} 4m-1-i & \text{for}\ j=0,\\ 4m-1+i & \text{for}\ j=1,3,4,\\ 4m+\left\lceil \frac{m}{2}\right\rceil +1-i & \text{for}\ j=2,\\ 3m+2i & \text{for}\ j=5,6, \end{cases}\] and if \(i=1,2,\dots,m\) then \[h_j(u_iv_i)=\begin{cases} 4m-2+i & \text{for}\ j=0,\\ 2m+\frac{i+1}{2} & \text{for}\ j=1,3,5 \ \text{and} \ i\ \text{odd},\\ 2m+\left\lceil \frac{m}{2}\right\rceil+\frac{i}{2} & \text{for}\ j=1,3,5 \ \text{and} \ \ i\ \text{even},\\ 2m+i & \text{for}\ j=2,4,6. \end{cases}\] It is not difficult to see that every edge labeling \(h_j\), \(j=0,1,2,\dots, 6\), admits the values from \(2m+1\) up to \(5m-2\). Thus every edge labeling \(h_j\), \(j=0,1,2,\dots, 6\), together with vertex labeling \(h\) has properties of a total labeling of the ladder \(L_m\). Let \[\begin{aligned} w_{h_j}= h_j(u_{i}u_{i+1})+h_j(v_{i}v_{i+1})+h_j(u_{i}v_{i})+h_j(u_{i+1}v_{i+1}) \label{edge-weight} \end{aligned}\tag{2}\] be partial weights of cycles \(C_4^{(i)}\) for every \(i=1,2,\dots,m-1\) and \(j=0,1,\dots,6\). Then according to (1) and (2) we get \[\begin{aligned} wt_{h_j}(C_4^{(i)})&= w_h+ w_{h_j} = 4m+2 + w_{h_j}. \end{aligned}\tag{3}\]

For \(j=0\), \(w_{h_0}=15m-4\) and \(wt_{h_0}(C_4^{(i)}) = 19m-2\) for every \(i=1,2,\dots, m-1\). Thus the total labeling \(h\cup h_0\) is \(C_4\)-supermagic for \(L_m\).

For \(j=1\), \(w_{h_1}=12m+ \left\lceil \frac{m}{2}\right\rceil +i\) and \(wt_{h_1}(C_4^{(i)}) = 16m+\left\lceil \frac{m}{2}\right\rceil +2+i\) for every \(i=1,2,\dots, m-1\). Under the labeling \(h\cup h_1\) the \(C_4\)-weights of \(L_m\) are consecutive integers and \(L_m\) is a super \((16m+\left\lceil \frac{m}{2}\right\rceil +3,1)\)\(C_4\)-antimagic.

For \(j=2\), \(w_{h_2}=11m+ \left\lceil \frac{m}{2}\right\rceil +2+2i\) and \(wt_{h_2}(C_4^{(i)}) = 15m+\left\lceil \frac{m}{2}\right\rceil +4+2i\) for every \(i=1,2,\dots, m-1\) and it proves that the total labeling \(h\cup h_2\) is a super \((15m+\left\lceil \frac{m}{2}\right\rceil +6,2)\)\(C_4\)-antimagic.

For \(j=3\), \(w_{h_3}=11m+ \left\lceil \frac{m}{2}\right\rceil +3i\) and \(wt_{h_3}(C_4^{(i)}) = 15m+\left\lceil \frac{m}{2}\right\rceil +2+3i\) for every \(i=1,2,\dots, m-1\). It shows that the labeling \(h\cup h_3\) is a super \(C_4\)-antimagic with the difference \(d=3\).

For \(j=4\), \(w_{h_4}=11m+ 4i\) and \(wt_{h_4}(C_4^{(i)}) = 15m+2+4i\) for every \(i=1,2,\dots, m-1\). Under the labeling \(h\cup h_4\) the \(C_4\)-weights of \(L_m\) form the arithmetic sequence with the difference \(d=4\) and \(L_m\) is a super \((15m+6,4)\)\(C_4\)-antimagic.

For \(j=5\), \(w_{h_5}=10m+ \left\lceil \frac{m}{2}\right\rceil +5i\) and \(wt_{h_5}(C_4^{(i)}) = 14m+\left\lceil \frac{m}{2}\right\rceil +2+5i\) for every \(i=1,2,\dots, m-1\). It shows that the labeling \(h\cup h_5\) is a super \(C_4\)-antimagic with the difference \(d=5\).

For \(j=6\), \(w_{h_6}=10m+ 6i\) and \(wt_{h_6}(C_4^{(i)}) = 14m+2+6i\) for every \(i=1,2,\dots, m-1\) and it proves that the total labeling \(h\cup h_6\) is a super \((14m+8,2)\)\(C_4\)-antimagic. This completes the proof. ◻

Next theorem proves a super \(C_4\)-antimagicness for ladder graph with differences \(7\le d \le 15\).

Theorem 2. Let \(m \geq 3\) be a positive integer. Then the ladder \(L_m\) is a super \((a,d)\)\(C_4\)-antimagic for every \(d \in \{7,8,9,10,11,12,13,14,15\}\).

Proof. Define a vertex labeling \(h: V(L_m)\to \{1,2,\dots, 2m\}\) such that \[\begin{aligned} h(u_i)&= 2i-1& \text{if }\ i=1, 2, \dots,m,\\ h(v_i)&= 2i& \text{if }\ i=1, 2, \dots,m. \end{aligned}\] For partial weights of \(C_4^{(i)}\) for every \(i=1,2,\dots,m-1\) we get \[\begin{aligned} w_h= h(u_i)+h(u_{i+1}) + h(v_i)+h(v_{i+1}) = 8i+2. \label{next-vertex-weight} \end{aligned}\tag{4}\]

We construct the labelings \(h_j\), \(j=7,8,\dots, 15\), for the edges of \(L_m\) as follows:
if \(i=1,2,\dots,m-1\) then \[h_j(u_iu_{i+1})=\begin{cases} 4m-i & \text{for}\ j=7,9,\\ 3m+i & \text{for}\ j=8,11,12,\\ 2m+2i-1 & \text{for}\ j=10,14,\\ 3m-1+2i & \text{for}\ j=13,\\ 2m+2i & \text{for}\ j=15, \end{cases}\] \[h_j(v_iv_{i+1})=\begin{cases} 5m-1-i & \text{for}\ j=7,\\ 4m-1+i & \text{for}\ j=8,9,11,12,15,\\ 2m+2i & \text{for}\ j=10,14,\\ 3m+2i & \text{for}\ j=13, \end{cases}\] and if \(i=1,2,\dots,m\) then \[h_j(u_iv_i)=\begin{cases} 2m+\frac{i+1}{2} & \text{for}\ j=7,9,11,13 \ \text{and} \ i\ \text{odd},\\ 3m-2+\frac{i}{2} & \text{for}\ j=7,9,11,13 \ \text{and} \ \ i\ \text{even},\\ 3m+1-i & \text{for}\ j=8,\\ 5m-1-i & \text{for}\ j=10,\\ 2m+i & \text{for}\ j=12,\\ 4m-2+i & \text{for}\ j=14,\\ 2m-1+2i & \text{for}\ j=15. \end{cases}\] One can see that for \(j=7,8,9,\dots,15\) every edge labeling \(h_j\) attains the values from the set \(\{2m+1,2m+2,\dots,5m-2\}\) and every labeling \(h\cup h_j\) satisfies the properties of a total labeling of the ladder \(L_m\). Then according to (2) and (4) we get \[\begin{aligned} wt_{h_j}(C_4^{(i)})&= w_h+ w_{h_j} = 8i+2 + w_{h_j}. \end{aligned}\tag{5}\]

For \(j=7\), \(w_{h_7}=14m-i-2\) and \(wt_{h_7}(C_4^{(i)}) = 14m+7i\) for every \(i=1,2,\dots, m-1\). Under the labeling \(h\cup h_7\) the \(C_4\)-weights of \(L_m\) create the arithmetic progression of the difference \(d=7\) and \(L_m\) is a super \((14m+7,7)\)\(C_4\)-antimagic.

For \(j=8\), \(w_{h_8}=13m\) and \(wt_{h_8}(C_4^{(i)}) = 13m+2+8i\) for every \(i=1,2,\dots, m-1\) and it proves that the total labeling \(h\cup h_8\) is a super \((13m+10,8)\)\(C_4\)-antimagic.

For \(j=9\), \(w_{h_9}=13m-2+i\) and \(wt_{h_9}(C_4^{(i)}) = 13m+9i\) for every \(i=1,2,\dots, m-1\). It shows that the labeling \(h\cup h_9\) is a super \(C_4\)-antimagic with the difference \(d=9\).

For \(j=10\), \(w_{h_{10}}=14m-4+2i\) and \(wt_{h_{10}}(C_4^{(i)}) = 14m-2+10i\) for every \(i=1,2,\dots, m-1\). Under the labeling \(h\cup h_{10}\) the \(C_4\)-weights of \(L_m\) form the arithmetic sequence with the difference \(d=10\) and \(L_m\) is a super \((14m+8,10)\)\(C_4\)-antimagic.

For \(j=11\), \(w_{h_{11}}=12m-2+ 3i\) and \(wt_{h_{11}}(C_4^{(i)}) = 12m+11i\) for every \(i=1,2,\dots, m-1\) and it proves that the total labeling \(h\cup h_{10}\) is a super \((12m+11,11)\)\(C_4\)-antimagic.

For \(j=12\), \(w_{h_{12}}=11m+ 4i\) and \(wt_{h_{12}}(C_4^{(i)}) = 11m+2+12i\) for every \(i=1,2,\dots, m-1\) and it proves that the total labeling \(h\cup h_{12}\) is a super \((11m+14,12)\)\(C_4\)-antimagic.

For \(j=13\), \(w_{h_{13}}=11m-2+5i\) and \(wt_{h_{13}}(C_4^{(i)}) = 11m+13i\) for every \(i=1,2,\dots, m-1\). It shows that the labeling \(h\cup h_{13}\) is a super \(C_4\)-antimagic with the difference \(d=13\).

For \(j=14\), \(w_{h_{14}}=12m-4+6i\) and \(wt_{h_{14}}(C_4^{(i)}) = 12m-2+14i\) for every \(i=1,2,\dots, m-1\). Under the labeling \(h\cup h_{14}\) the \(C_4\)-weights of \(L_m\) form the arithmetic sequence with the difference \(d=14\) and \(L_m\) is a super \((12m+12,14)\)\(C_4\)-antimagic.

For \(j=15\), \(w_{h_{15}}=10m-1+7i\) and \(wt_{h_{15}}(C_4^{(i)}) = 10m+1+15i\) for every \(i=1,2,\dots, m-1\). It shows that the labeling \(h\cup h_{15}\) is a super \(C_4\)-antimagic with the difference \(d=15\).

Thus we have arrived at the desired result. ◻

References

  1. Gutiérrez, A., & Lladó, A. (2005). Magic coverings. Journal of Combinatorial Mathematics and Combinatorial Computing, 55(2005), 43-56.

  2. Kotzig, A., & Rosa, A. (1970). Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13(4), 451-461.

  3. Enomoto, H., Lladó, A. S., Nakamigawa, T., & Ringel, G. (1998). Super edge-magic graphs. Sut J. Math, 34(2), 105-109.

  4. Maryati, T. K., Baskoro, E. T., & Salman, A. N. M. (2008). \(P_h\)-(super)magic labelings of some trees. Journal of Combinatorial Mathematics and Combinatorial Computing, 65, 198-204.

  5. Lladó, A., & Moragas, J. (2007). Cycle-magic graphs. Discrete Mathematics, 307(23), 2925-2933.

  6. Maryati, T. K., Salman, A. N. M., & Baskoro, E. T. (2013). Supermagic coverings of the disjoint union of graphs and amalgamations. Discrete Mathematics, 313(4), 397-405.

  7. Ngurah, A. A. G., Salman, A. N. M., & Susilowati, L. (2010). H-supermagic labelings of graphs. Discrete Mathematics, 310(8), 1293-1300.

  8. Jeyanthi, P., & Selvagopal, P. (2010). More classes of H-supermagic graphs. International Jornal of Algorithms, Computing and Mathematics, 3(1), 93-108.

  9. Inayah, N., Lladó, A., & Moragas, J. (2012). Magic and antimagic H-decompositions. Discrete Mathematics, 312(7), 1367-1371.

  10. Inayah, N., Salman, A. N. M., & Simanjuntak, R. (2009). On \((a, d)\)\(H\)-antimagic coverings of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 71, 273-281.

  11. Inayah, N., Simanjuntak, R., Salman, A. N. M., & Syuhada, K. I. A. (2013). Super \((a, d)\)\(H\)-antimagic total labelings for shackles of a connected graph \(H\). Australasian Journal of Combinatorics, 57, 127-138.

  12. Miller, M., & Semaničová-Feňovčíková, A. (2015). A Construction of H-antimagic Graphs. Acta Mechanica Slovaca 19(3), 6-11.

  13. Bača, M., Miller, M., Ryan, J., & Semaničová-Feňovčíková, A. (2016). On \(H\)-antimagicness of disconnected graphs. Bulletin of the Australian Mathematical Society, 94(2), 201-207.

  14. Lih, K. W. (1983). On magic and consecutive labelings of plane graphs. Utilitas Math, 24, 165-197.

  15. Bača, M., Brankovic, L., & Semaničová-Feňovčíková, A. (2011). Labelings of plane graphs containing Hamilton path. Acta Mathematica Sinica, English Series, 27(4), 701-714.

  16. Bača, M., Miller, M., Phanalasy, O., & Semaničová-Feňovčíková, A. (2010). Super d-antimagic labelings of disconnected plane graphs. Acta Mathematica Sinica, English Series, 26(12), 2283-2294.

  17. Simanjuntak, R., Miller, M., & Bertault, F. (2000). Two new \((a, d)\)-antimagic graph labelings. Proc. Eleventh Australas. Workshop Combin. Alg. (AWOCA), 179-189.

  18. Bača, M., & Miller, M. (2008). Super edge-antimagic graphs: A wealth of problems and some solutions. Universal-Publishers.

  19. Figueroa-Centeno, R. M., Ichishima, R., & Muntaner-Batle, F. A. (2001). The place of super edge-magic labelings among other classes of labelings. Discrete Mathematics, 231(1-3), 153-168.

  20. Wallis, W. D. (2001). Magic graphs. Birkhäuser, New York.

  21. Arumugam, S., Miller, M., Phanalasy, O., & Ryan, J. (2014). Antimagic labeling of generalized pyramid graphs. Acta Mathematica Sinica, English Series, 30(2), 283-290.