A supermagic labeling (often also called vertex-magic edge labeling) of a graph \(G(V,E)\) with \(|E|=q\) is a bijection from \(E\) to the set of first \(k\) positive integers such that the sum of labels of all incident edges of every vertex \(x\in V\) is equal to the same integer \(c\). An existence of a supermagic labeling of Cartesian product of two cycles, \(C_{n}\Box C_m\) for \(n,m\geq4\) and both \(n,m\) even and for any \(C_n\Box C_n\) with \(n\geq3\) was proved by Ivančo. Ivančo also conjectured that such labeling is possible for any \(C_n\Box C_m\) with \(n,m\geq3\). We prove his conjecture for all \(n,m\) odd that are not relatively prime.
A labeling of a graph \(G\) with vertex set \(V\) of order \(p\) and edge set \(E\) of order \(q\) is a bijection \(f\) from \(V, E,\) or \(V\cup E\) to the set \(\{1,2,\dots,s\}\) where \(s=p,q\), or \(p+q\), respectively, assigning to each element \(a\) of \(V, E,\) or \(V\cup E\) its label \(f(a)\).
The weight of an element is defined as the sum of labels of all adjacent or incident elements (or both), sometimes including the label of the element itself.
A magic type labeling is one in which the weight of every vertex or edge of \(G\) is equal to the same integer \(c\), called the magic constant. Recently many authors studied also labelings using Abelian groups rather than sets of consecutive integers. Such labelings are then usually called \(\Gamma\)-labelings.
Probably the longest studied magic type labeling is the supermagic labeling, also called the vertex-magic edge labeling. To maintain consistency with previous results on Cartesian product of two cycles, we use the former.
Definition 1.1. Let \(G\) be a graph with vertex set \(V\) and edge set \(E\) of order \(q\), and \(f\) a bijection from \(E\) to the set of integers \(\{1,2,\dots, q\}\), called labels. Define the weight \(w(x)\) of a vertex \(x\in V\) as the sum of labels of all edges incident with \(x\). It the weight os every vertex is the same, that is, there is a positive integer \(c\) called the magic constant such that \[w(x)=\sum_{xy\in E} f(xy)=c \ \ {\text{for all} \ x\in V},\] then the mapping \(f\) is called a supermagic labeling or supermagic labeling of graph \(G\).
There are too many papers studying the supermagic labelings of graphs to be listed here. For a comprehensive overview, we refer the interested reader to Gallian’s survey [7]. Vertex-transitive graphs are some of most interesting classes in this context. Ivančo studied Cartesian products of two cycles.
Definition 1.2. The Cartesian product \(G=G_{1}\Box G_{2}\) of graphs \(G_{1}\) and \(G_{2}\) with disjoint vertex and edge sets \(V_{1}\), \(V_{2}\), and \(E_{1}\), \(E_{2}\), respectively, is the graph with vertex set \(V=V_{1} \times V_{2}\) where any two vertices \(u=(u_{1},u_{2})\in G\) and \(v=(v_{1},v_{2})\in G\) are adjacent in \(G\) if and only if either \(u_{1}=v_{1}\) and \(u_{2}\) is adjacent with \(v_{2}\) in \(G_{2}\) or, \(u_{2}=v_{2}\) and \(u_{1}\) is adjacent with \(v_{1}\) in \(G_{1}\).
In [8], Ivančo proved the following results.
Theorem 1.3(Ivančo [8]).The Cartesian product \(C_{n} \Box C_{n}\) has a supermagic labeling for any \(n\geq 3\).
Theorem 1.4(Ivančo [8]). Let \(n,m \geq 2\) be integers. Then the Cartesian product \(C_{2n} \Box C_{2m}\) has a supermagic labeling.
Ivančo also conjectured that the Cartesian product \(C_{n} \Box C_{m}\) allows a supermagic labeling for any \(n,m\geq 3\).
Conjecture 1.5(Ivančo [8]).The Cartesian product \(C_{n} \Box C_{m}\) has a supermagic labeling for any \(n,m\geq 3\).
It turns out that when the labeling is performed in a cyclic group \(Z_{2nm}\) rather than in positive integers, the conjecture is true.
Definition 1.6. A \(\Gamma\)-supermagic labeling of a graph \(G(V,E)\) with \(|E|=q\) is a bijection \(f\) from \(E\) to an Abelian group \(\Gamma\) of order \(k\) such that the sum of labels of all incident edges of every vertex \(x\in V\), called the weight of \(x\) and denoted \(w(x)\), is equal to the same element \(\mu \in \Gamma\), called the magic constant. That is, \[w(x) =\sum_{xy\in E} f(xy) =\mu\] for every vertex \(x\in V\).
Froncek, McKeown, McKeown, and McKeown in [3] proved the following.
Theorem 1.7([3]).The Cartesian product \(C_n \Box C_m\) admits a \(Z_{2nm}\)-supermagic labeling for all \(n,m\geq 3\).
Recently, Froncek, Paananen and Sorensen [5, 6] expanded the result to general Abelian groups.
Theorem 1.8([5, 6]).The Cartesian product \(C_n \Box C_m\) admits a \(\Gamma\)-supermagic labeling for any Abelian group of order \(2nm\) when \(n,m>1\) are both odd, or \(n,m>2\) are both even.
We will show that Ivančo’s conjecture is true for cycles of odd lengths that are not relatively prime by proving the following.
Theorem 1.9. Let \(n,m\) be odd positive integers with \(\gcd(n,m)>1\). Then there exists a supermagic labeling of the Cartesian product \(C_n\Box C_m\) with the magic constant \(c=4nm+2\).
The construction is based on a similar one used for \(Z_{2nm}\)-labeling of \(C_n\Box C_m\) in [4] by Froncek and McKeown.
Since Ivančo’s proof in [8] was strictly existential and did not provide a construction of a particular labeling, we also present a labeling for the case covered by Theorem 1.4.
For completeness we also mention that analogous results for distance magic and \(\Gamma\)-distance magic labeling of \(C_n\Box C_m\) (where we label vertices rather than edges and the weight of a vertex \(x\) is the sum of labels of all neighbors of \(x\)) were proved in [10], [2], and [1].
We use the following notation. Vertices will be denoted \(x_{ij}\) for \(i=1,2,\dots,n\) and \(j=1,2,\dots,m\). Every vertex \(x_{ij}\) is then incident with two vertical edges \(x_{(i-1)j}x_{ij}\) and \(x_{ij}x_{(i+1)j}\) and two horizontal edges \(x_{i(j-1)}x_{ij}\) and \(x_{ij}x_{i(j+1)}\) where the subscripts are computed modulo \(n\) and \(m\), respectively, with 0 replaced by \(n\) and \(m\) as appropriate. This means in particular that vertices \(x_{im}\) are incident with horizontal edges \(x_{i(m-1)}x_{im}\) and \(x_{im}x_{i1}\) and similarly vertices \(x_{nj}\) are incident with vertical edges \(x_{(n-1)j}x_{nj}\) and \(x_{nj}x_{1j}\).
By a diagonal \(D^j\) we mean a cycle consisting alternately of horizontal and vertical edges containing the horizontal edge \(x_{1j}x_{1(j+1)}\).
More precisely, in terms of edges we have \[D^{j}=(x_{1j}x_{1(j+1)},x_{1(j+1)}x_{2(j+1)},x_{2(j+1)}x_{2(j+2)},x_{2(j+2)}x_{3(j+2)},\dots,x_{nj}x_{1j}).\]
Or, in terms of vertices we can write \[D^{j}=x_{1j},x_{1(j+1)},x_{2(j+1)},x_{2(j+2)},x_{3(j+2)},\dots,x_{nj},x_{1j}.\]
We observe that each diagonal \(D^j\) is a cycle of length \(2l\), where \(l=\mathrm{lcm}(n,m)\). To see that, we notice that to get back to \(x_{1j}\) we need to pass through \(am\) horizontal edges and \(bn\) vertical edges, where \(a,b\) are positive integers. Because the number of horizontal and vertical edges in the diagonal is the same, we must have \(am=bn=l\) and the conclusion follows. Since each diagonal has \(2l\) edges, the number of diagonals, call it \(d\), is \(d=2nm/2l=nm/l=\gcd(n,m)\).
To avoid complicated notation in vertex subscripts, we just denote the horizontal edges in \(D^j\) consecutively as \(h^j_1,h^j_2,\dots,h^j_{l}\) and the vertical ones by \(v^j_1,v^j_2,\dots,v^j_{l}\). All diagonals will start at vertex \(x_{1j}\), that is, \(h^j_1=x_{1j}x_{1(j+1)},v^j_1=x_{1(j+1)}x_{2(j+1)}\) and so on. We will also call the pair of consecutive edges \((h^j_k,v^j_k)\) the \(HV\)-corner and the pair \((v^j_{k-1},h^j_{k})\) the VH-corner. In particular, the pairs will be called the \(k\)-th \(HV\)-corner and \(k\)-th \(VH\)-corner, respectively. Note that the first \(HV\)-corner is \((h^j_1,v^j_1)\) while the first \(VH\)-corner is \((v^j_l,h^j_1)\).
We present examples for \(C_3\Box C_9\) with three diagonals of length 9 and \(C_8\Box C_{12}\) with four diagonals of length 24 in Figures 1 and 2, respectively.
Construction 2.1. We construct a supermagic labeling \(f\) of \(C_n\Box C_m\) for \(3\leq n\leq m\), where \(n,m\) are odd and \(\gcd(n,m)>1\).
Since \(n,m\) are odd, we have both \(l\) and \(d\) odd and because we have assumed that \(n\) and \(m\) are not co-prime, we have \(d\geq3\). We set \(l=2l'+1\).
We label each diagonal \(D^j\) for \(j=1,2,\dots,d-1\) alternately with two sets of \(l\) consecutive integers. The horizontal edges will be labeled in increasing order and the vertical ones in decreasing order. The last diagonal \(D^d\) will be labeled differently.
All diagonals except \(D^1\) will start at vertex \(x_{1j}\). Hence, we have \(h^j_1=x_{1j}x_{1(j+1)},v^j_1=x_{1(j+1)}x_{2(j+1)}\) and so on. For \(D^1\), we start at vertex \(x_{1(d+1)}\), obtaining \(h^1_1=x_{1(d+1)}x_{1(d+2)},v^1_1=x_{1(d+2)}x_{2(d+2)}\) and so on. Recall that the first \(HV\)-corner is \((h^j_1,v^j_1)\) while the first \(VH\)-corner is \((v^j_l,h^j_1)\).
For all diagonals except the last two we use the same pattern. We assign an increasing sequence with common difference one on the horizontal edges, and a decreasing sequence on the vertical edges. The sequences on horizontal edges start at edge \(x_{1j}x_{1(j+1)}=h^j_1\) for \(j\) odd and at \(x_{2j}x_{2(j+1)}=h^j_2\) for \(j\) even. On the vertical edges, the sequence starts at edge \(x_{1(j+1)}x_{2(j+1)}=v^j_1\) for all diagonals \(D^j, 1\leq j\leq d-2\). This guarantees that the partial corner weights will be constant except at the starting vertex \(x_{1,j}\) for \(j\) odd.
The odd diagonals except the last one will be labeled as follows.
\[\label{eq:D^j-odd} % D^j \ \text{for}\ j\ \text{odd}, \ j<d\ \begin{cases} f(h^j_k)= (j-1)l + k,\\ \\ f(v^j_k)= 2nm – (j-1)l -k +1.\\ \end{cases} %\]
Now we look at the partial weights created by the labels in each \(D^j\). At the \(k\)-th \(HV\)-corner, we have the partial weight \(w^j_{HV}\) of the appropriate vertex of \(D^j\) equal to \[\begin{aligned} \label{eq:D^j-odd-HV-k} w^j_{HV}(x_{st}) &= f(h^j_k)+f(v^j_k)\nonumber\\ &= ((j-1)l + k) + (2nm – (j-1)l -k +1) = 2nm+1, \end{aligned} \tag{1}\] where \(s=k\mod n\) and \(t=k\mod m\).
At the first \(VH\) corner for \(j=1\) we have \[\begin{aligned} \label{eq:D^j-odd-VH-first-j=1} w^1_{VH}(x_{1(d+1)})&= f(v^1_l) + f(h^1_{1})= (2nm – l +1) + 1 = 2nm-l+2, % \end{aligned} \tag{2}\] and for \(3\leq j\leq d-2\) we have \[\begin{aligned} \label{eq:D^j-odd-VH-first} w^j_{VH}(x_{1j}) &= f(v^j_l) + f(h^j_{1})\nonumber\\ &= (2nm – (j-1)l -l +1) + ((j-1)l + 1) = 2nm-l+2, \end{aligned} \tag{3}\] as well. At the \(k\)-th \(VH\)-corner for \(2\leq k\leq l\) the partial weight \(w^j_{VH}\) is \[\begin{aligned} \label{eq:D^j-odd-VH-k>1} w^j_{VH}(x_{st}) &= f(v^j_{k-1}) + f(h^j_{k})\nonumber\\ &= (2nm – (j-1)l -(k-1) +1) + ((j-1)l + k) = 2nm+2, \end{aligned} \tag{4}\] regardless of the value of \(j\).
Now we want to label the even diagonals so that their \(VH\)-corners would have partial weights equal to \(2nm+1\), the weights of \(HV\)-corners would be \(2nm\) or \(2nm+l\) (at one “exceptional” corner) and the vertices with exceptional weights would be aligned. To do so, we need to shift the horizontal edge labels by one position down, while labeling the vertical edges as before. Namely, for \(j<d-1\) we have \[\label{eq:D^j-even} % D^j \ \text{for}\ j\ \text{even} \ \begin{cases} f(h^j_1)= (j-1)l + l=jl,\\ %\\ f(h^j_k)= (j-1)l + k-1 \ \text{for}\ k>1,\\ %\\ f(v^j_k)= 2nm – (j-1)l -k +1.\\ \end{cases} %\]
The partial weights at the first (exceptional) \(HV\)-corner are then \[\begin{aligned} \label{eq:D^j-even-HV-first} w^j_{HV}(x_{1(j+1)}) &= f(h^j_1)+f(v^j_1)= ((j-1)l + l) + (2nm – (j-1)l) = 2nm+l, \end{aligned} \tag{5}\] and at the \(k\)-th \(HV\)-corner for \(k>1\) we have \[\begin{aligned} \label{eq:D^j-even-HV-k>1} w^j_{HV}(x_{st}) &= f(h^j_k)+f(v^j_k)\nonumber\\ &= ((j-1)l + k-1) + (2nm – (j-1)l -k +1) = 2nm. \end{aligned} \tag{6}\]
At the \(k\)-th \(VH\)-corner the partial weight \(w^j_{VH}\) is \[\begin{aligned} \label{eq:D^j-even-VH-k} w^j_{VH}(x_{st}) &= f(v^j_{k-1}) + f(h^j_{k})\nonumber\\ &= (2nm – (j-1)l -(k-1) +1) + ((j-1)l + k-1) = 2nm+1, \end{aligned} \tag{7}\] for any value of \(j\). The last even diagonal \(D^{d-1}\) is labeled in a similar way except that the vertex with exceptional partial weight is shifted. We recall that the exceptional vertices on the seams between consecutive even and odd diagonals were all placed on the first horizontal cycle \(C_m\). That is, at the first \(HV\)-corner. In the case of the last even diagonal, we place it roughly in the middle of the diagonal, at the \((l'+2)\)-nd corner. Namely, we have \[\label{eq:D^j-(d-1)} % %D^j \ \text{for}\ j=d-1 \ D^{d-1} \ \begin{cases} f(h^{d-1}_k)= (d-2)l + k+l'-1 \ \text{for}\ k\leq l'+2\\ %\\ f(h^{d-1}_k)= (d-2)l + k-l'-2 \ \text{for}\ k\geq l'+3\\ %\\ f(v^{d-1}_k)= 2nm – (d-2)l -k-l' +1 \ \text{for}\ k\leq l'+1\\ %\\ f(v^{d-1}_k)= 2nm – (d-2)l -k+l'+2 \ \text{for}\ k\geq l'+2.\\ \end{cases} %\]
The partial weights at the first \(l'+1\) \(HV\)-corners are \[\begin{aligned} \label{eq:D^{d-1}-HV-first} w^{d-1}_{HV}(x_{st}) &= f(h^{d-1}_k)+f(v^{d-1}_k)\nonumber\\ &= ((d-2)l+k+l'-1) + (2nm-(d-2)l -k-l'+1) \nonumber\\ &= 2nm, \end{aligned} \tag{8}\] and at the \((l'+2)\)-nd \(HV\)-corner we get the exceptional weight \[\begin{aligned} \label{eq:D^{d-1}-HV-k=l'+2} w^{d-1}_{HV}(x_{st}) &= f(h^{d-1}_{l'+2})+f(v^{d-1}_{l'+2})\nonumber\\ &= ((d-2)l+(l'+2) +l'-1) + (2nm-(d-2)l -(l'+2)+l'+2) \nonumber\\ &= ((d-2)l+l) + (2nm-(d-2)l) = 2nm+l. \end{aligned} \tag{9}\]
At the remaining \(HV\)-corners for \(k=l'+3,l'+4,\dots,l\) the weights are again \[\begin{aligned} \label{eq:D^{d-1}-HV-last} w^{d-1}_{HV}(x_{st}) &= f(h^{d-1}_{l'+2})+f(v^{d-1}_{l'+2})\nonumber\\ &= ((d-2)l+k-l'-2) + (2nm-(d-2)l -k+l'+2) \nonumber\\ &= 2nm. \end{aligned} \tag{10}\]
At the \(VH\)-corners, the partial weights \(w^{d-1}_{VH}\) are as follows. For \(k=1\) we have \[\begin{aligned} \label{eq:D^{d-1}-VH-k=1} w^{d-1}_{VH}(x_{1(d-1)}) &= f(v^{d-1}_{l}) + f(h^{d-1}_{1})\nonumber\\ &= (2nm – (d-2)l -l+l'+2) +((d-2)l + 1+l'-1) \nonumber\\ &= 2nm-l+2l'+2 =2nm+1, \end{aligned} \tag{11}\] and for \(k=2,3,\dots,l'+2\) we have \[\begin{aligned} \label{eq:D^{d-1}-VH-first} w^{d-1}_{VH}(x_{st}) &= f(v^{d-1}_{k-1}) + f(h^{d-1}_{k})\nonumber\\ &= (2nm – (d-2)l -(k-1)-l' +1) + ((d-2)l + k+l'-1) \nonumber\\ &= 2nm+1. \end{aligned} \tag{12}\]
For \(k=l'+3,l'+4,\dots,l\), \[\begin{aligned} \label{eq:D^{d-1}-VH-last} w^{d-1}_{VH}(x_{st})&= f(v^{d-1}_{k-1}) + f(h^{d-1}_{k})\nonumber\\ &= (2nm – (d-2)l -(k-1)+l'+2) +((d-2)l + k-l'-2) \nonumber\\ &= 2nm+1, \end{aligned} \tag{13}\] as in all previous cases.
We present an example of non-exceptional corners in Figure 3. The blue edges belong to an odd diagonal other than \(D^d\) and the green edges to an even diagonal.
The remaining odd diagonal, \(D^d\), is labeled in a different way. We define \[\label{eq:D^j-d} % %D^j \ \text{for}\ j=d-1 \ D^{d} \ \begin{cases} f(h^{d}_1)= dl \\ %\\ f(h^{d}_k)= (d-1)l + 2k-2 \ \text{for}\ 2\leq k\leq l'+1\\ %\\ f(h^{d}_k)= (d-2)l + 2k-2 \ \text{for}\ k\geq l'+2\\ %\\ f(v^{d}_k)= 2nm – (d-1)l -2k+2 \ \text{for}\ k\leq l'+1\\ %\\ f(v^{d}_k)= 2nm – (d-2)l – 2k+2 \ \text{for}\ k\geq l'+2.\\ \end{cases}\]
The partial weight at the first \(HV\)-corner is \[\begin{aligned} \label{eq:D^d-HV-first} w^{d}_{HV}(x_{1(d+1)}) &= f(h^{d}_1)+f(v^{d}_1)\nonumber\\ &= dl + (2nm – (d-1)l -2+2) \nonumber\\ &= 2nm +l, \end{aligned} \tag{14}\] and at the \(k\)-th \(HV\)-corner for \(k=2,3,\dots, l'+1\) as \[\begin{aligned} \label{eq:D^d-HV-k<l'+2} w^{d}_{HV}(x_{st}) &= f(h^{d}_{k})+f(v^{d}_{k})\nonumber\\ &= ((d-1)l + 2k-2) + (2nm – (d-1)l -2k+2) \nonumber\\ &= 2nm. \end{aligned} \tag{15}\]
At the remaining \(HV\)-corners for \(k=l'+2,l'+3,\dots,l\) the weights are \[\begin{aligned} \label{eq:D^d-HV-last} w^{d}_{HV}(x_{st}) &= f(h^{d}_{k})+f(v^{d}_{k})\nonumber\\ &= ((d-2)l + 2k-2) + (2nm – (d-2)l -2k+2) \nonumber\\ &= 2nm, \end{aligned} \tag{16}\] as well. At the \(VH\)-corners, the partial weights \(w^{d}_{VH}\) are as follows. For \(k=1\) we have \[\begin{aligned} \label{eq:D^d-VH-k=1} w^{d}_{VH}(x_{1d}) &= {f(v^d_{l}) + f(h^d_{1})}\nonumber\\ &= (2nm – (d-2)l -2l+2) +dl \nonumber\\ &= 2nm+2, \end{aligned} \tag{17}\] and for \(k=2,3,\dots,l'+1\) we have \[\begin{aligned} \label{eq:D^d-VH-first} w^{d}_{VH}(x_{st}) &= f(v^d_{k-1}) + f(h^d_{k})\nonumber\\ &= (2nm – (d-1)l -2(k-1)+2) + ((d-1)l + 2k-2) \nonumber\\ &= 2nm+2, \end{aligned} \tag{18}\] as well. For \(k=l'+2\) we obtain the exceptional weight \[\begin{aligned} \label{eq:D^d-VH-k=l'+2} w^{d}_{VH}(x_{st}) &= f(v^d_{l'+1}) + f(h^d_{l'+2})\nonumber\\ &= (2nm – (d-1)l -2(l'+1)+2) + ((d-2)l + 2(l'+2)-2) \nonumber\\ &= (2nm – (d-1)l -2l') + ((d-2)l + 2l'+2) \nonumber\\ &= 2nm-l+2. \end{aligned} \tag{19}\]
Recall that by (9) the \(HV\)-corner at vertex \(x_{st}\) (where where \(s=(l'+2)\mod n\) and \(t=(l'+2)\mod m\)) is formed by edges \(h^{d-1}_{l'+2}\) and \(v^{d-1}_{l'+2}\) with \(w^{d}_{HV}(x_{st})=2nm+l\). Finally, for \(k=l'+3,l'+4,\dots,l\), \[\begin{aligned} \label{eq:D^d-VH-last} w^{d}_{VH}(x_{st}) &= f(v^d_{k-1}) + f(h^d_{k})\nonumber\\ &= (2nm – (d-2)l – 2(k-1)+2) +((d-2)l + 2k-2) \nonumber\\ &= 2nm+2 \end{aligned} \tag{20}\]
as in all previous cases except \(k=l'+2\).
0◻
We present a labeling of \(C_5\Box C_5\) in Figure 4. Exceptional vertices are in solid colors. The odd diagonals except \(D^5\) are blue, the even ones are green. The last odd diagonal \(D^5\) is red. It can be readily checked that the magic constant is \[c = 4nm + 2 = 102\] as shown in Construction 2.1.
We summarize the partial weights depending on the parity of the diagonals in the table below. We specifically point out the exceptional vertices.
\[\begin{array}{|l|l|c|c|c|c|} \hline & \text{parity}& \text{range} &w_{HV}(x^j_{st}) &w_{VH}(x^{j+1}_{st}) & w(x_{st}) \\ \hline \text{reg}&j \text{\ odd\ }& j<d&2nm+1 &2nm+1 &4nm+2 \\ \hline \text{exc}&j \text{\ even\ }&k=1 &2nm+l &2nm-l+2 &4nm+2 \\ \hline \text{reg}&j \text{\ even\ }&j<d-1,2\leq k\leq l &2nm &2nm+2 &4nm+2 \\ \hline \text{reg}&j\text{\ even\ }&j=d-1, k\neq l'+2 &2nm &2nm+2 &4nm+2 \\ \hline \text{exc}&j\text{\ even\ }&j=d-1, k=l'+2 &2nm+l &2nm-l+2 &4nm+2 \\ \hline \text{exc}&j \text{\ odd}&j=d, k=1 &2nm+l &2nm-l+2 &4nm+2 \\ \hline \text{reg}&j \text{\ odd}&j=d, 2\leq k\leq l &2nm &2nm+2 &4nm+2 \\ \hline \end{array}\]The construction for \(n,m\) even is based on the same idea and is actually much simpler.
Construction 3.1. We construct a supermagic labeling \(f\) of \(C_n\Box C_m\) for \(4\leq n\leq m\), where \(n,m\) are even.
Because we have \(n,m\) both even, the number of diagonals \(d=\gcd(n,m)\) is also even. This fact simplifies matters a lot. The construction is very similar to the previous one. The only difference is that because we have an even number of diagonals, we will not need the exceptional one.
We label all odd diagonals as follows, which is the same as the first odd diagonals in Construction 2.1. The only difference is that we start each diagonal \(D^j\) at \(x_{1j}\), including \(D^1\), which will then of course start at \(x_{11}\).
\[\label{eq:even_D^j-odd} % D^j \ \text{for}\ j\ \text{odd}, \ j<d\ \begin{cases} f(h^j_k)= (j-1)l + k,\\ \\ f(v^j_k)= 2nm – (j-1)l -k +1.\\ \end{cases} %\]
The partial weights at the \(HV\)-corners are by (1) again equal to \[\begin{aligned} \label{eq:even_D^j-odd-HV-k} w^j_{HV}(x_{st}) &= 2nm+1. \end{aligned} \tag{21}\]
At the first \(VH\)-corner for we have \[\begin{aligned} \label{eq:even_D^j-odd-VH-first} w^j_{VH}(x_{1j}) &= f(v^j_l) + f(h^j_{1})\nonumber\\ &= (2nm – (j-1)l -l +1) + ((j-1)l + 1) = 2nm-l+2, \end{aligned} \tag{22}\] for every odd \(j\). At the \(k\)-th \(VH\)-corner for \(2\leq k\leq l\) the partial weight \(w^j_{VH}\) is by (3) \[\begin{aligned} \label{eq:even_D^j-odd-VH-k>1} w^j_{VH}(x_{st}) &= 2nm+2, \end{aligned} \tag{23}\] for every odd \(j\).
We again label the even diagonals so that their \(VH\)-corners have partial weights equal to \(2nm+1\), the weights of \(HV\)-corners are \(2nm\) or \(2nm+l\) (at the “exceptional” corner) and the vertices with exceptional weights match. \[\label{eq:even_D^j-even} % D^j \ \text{for}\ j\ \text{even} \ \begin{cases} f(h^j_1)= (j-1)l + l=jl,\\ %\\ f(h^j_k)= (j-1)l + k-1 \ \text{for}\ k>1,\\ %\\ f(v^j_k)= 2nm – (j-1)l -k +1.\\ \end{cases} %\]
The partial weights at the first \(HV\)-corner are then (5) \[\begin{aligned} \label{eq:even_D^j-even-HV-first} w^j_{HV}(x_{1(j+1)}) &= 2nm+l, \end{aligned} \tag{24}\] as in Construction 2.1 and similarly at the \(k\)-th \(HV\)-corner for \(k>1\) we have by (6) \[\begin{aligned} \label{eq:even_D^j-even-HV-k>1} w^j_{HV}(x_{st}) &= 2nm. \end{aligned} \tag{25}\]
At the \(k\)-th \(VH\)-corner the partial weight \(w^j_{VH}\) is \[\begin{aligned} \label{eq:even_D^j-even-VH-k} w^j_{VH}(x_{st}) &= 2nm+1, \end{aligned} \tag{26}\] for any even value of \(j\), as follows from (7). 0◻
We again present a labeling of a small example, \(C_4\Box C_4\) in Figure 5. Exceptional vertices are in solid color. The odd diagonals are blue, the even ones are green. It can be easily checked that the magic constant is \[c = 4nm + 2 = 66,\] as shown in Construction 3.1.
The partial weights depending on the parity of the diagonals are shown in the table below. We again point out the exceptional vertices.
\[\begin{array}{|l|l|c|c|c|c|} \hline & \text{parity}& \text{range} &w_{HV}(x^j_{st}) &w_{VH}(x^{j+1}_{st}) & w(x_{st}) \\ \hline \text{reg}&j \text{\ odd\ }& 1\leq j\leq d-1&2nm+1 &2nm+1 &4nm+2 \\ \hline \text{exc}&j \text{\ even\ }&k=1 &2nm+l &2nm-l+2 &4nm+2 \\ \hline \text{reg}&j \text{\ even\ }&2\leq j<d\leq k\leq l &2nm &2nm+2 &4nm+2 \\ \hline \end{array}\]
Now we are ready to prove our result. First we state a simple lemma tying together two consecutive diagonals.
Lemma 4.1. For each vertex \(x_{st}, 1\leq s\leq n, 1\leq t\leq m,\) there exists a unique pair \((j,k)\) such that \(x_{st}\) is the shared corner vertex between the edge-pair \((h^j_{k},v^j_{k})\) (the \(k\)-th \(HV\)-corner of diagonal \(D^j\)) and the edge-pair \((v^{j+1}_{k-1},h^{j+1}_{k})\) (the \(k\)-th \(VH\)-corner of diagonal \(D^{j+1}\)). In particular, \[j=(t-s)\mod{d} \ \ \text{and} \ \ k=s+\frac{t-s-j}{d}n.\]
Proof. It follows from the definition od diagonal \(D^1\) that the vertices
\(x_{12},x_{23},\dots\), \(x_{s(s+1)},\dots,x_{n(n+1)}\) belong to the
first \(n\) \(HV\)-corners formed by pairs of edges \[(x_{ii} x_{i(i+1)},x_{i(i+1)} x_{(i+1)(i+1)})=
(h^1_i,v^1_i).\]
If \(m>n\), then for any fixed \(s, 1\leq s\leq n\) also the vertices \(x_{s(s+qd+1)}\) where \(1\leq q\leq l-1\) are \(HV\)-corners of the diagonal \(D^1\). Therefore, the vertices \(x_{s(s+qd+j)}\) where \(0\leq q\leq l-1\) and \(1\leq j\leq d\) are \(HV\)-corners of the diagonal \(D^j\).
Now for every vertex \(x_{st}\) we can write \(t=s+qd+j\) for \(0\leq q\leq l-1\) and \(1\leq j\leq d\). Therefore, \(x_{st}=x_{s,(s+qd+j)}\) belongs to the \(j\)-th diagonal \(D^j\) and because \[t-s=s+qd+j-s= qd+j,\] we have \[j=(t-s)\mod{d}.\]
To verify the value of \(k\), we first observe that at the vertex \(x_{s(s+j)}\) we have the \(s\)-th \(HV\)-corner of the diagonal \(D^j\) and at the vertex \(x_{st}=x_{s(s+qd+j)}\) we have the \((s+qn)\)-th \(HV\)-corner of the diagonal \(D^j\) and \[\begin{aligned} \label{eq:k=s+qn} k=s+qn. \end{aligned} \tag{27}\]
But \[t=s+qd+j,\] which yields \[qd=t-s-j,\] and \[\begin{aligned} \label{eq:q=} q=(t-s-j)/d. \end{aligned} \tag{28}\] Combining equalities (27) and (28), we obtain \[k=s+\frac{t-s-j}{d}n,\] as desired. ◻
Having now all tools that we need, we can prove the following.
Theorem 4.2. Let \(n,m>2\) , be positive integers of the same parity with \(\gcd(n,m)>1\). Then the labeling \(f\) described in Constructions 2.1 and 3.1 is a supermagic labeling of the Cartesian product \(C_n\Box C_m\) with the magic constant \(c=4nm+2\).
Proof. We start by observing that every vertex \(x_{st}\) of \(C_n\Box C_m\) belongs to two consecutive diagonals, say \(D^j\) and \(D^{j+1}\). Moreover, the edges \(x_{s(t-1)}x_{st}\) and \(x_{st}x_{(s+1)t}\) form a \(k\)-th \(HV\)-corner in \(D^j\) for some \(k\) while the edges \(x_{(s-1)t}x_{st}\) and \(x_{st}x_{s(t+1)}\) form a \(k\)-th \(VH\)-corner in \(D^{j+1}\). It follows that the weight \(w(x_{st})\) is the sum of the partial weights, that is, \[w(x_{st}) = w^j_{HV}(x_{st}) + w^{j+1}_{VH}(x_{st}).\]
First we look at the case of \(n,m\) odd. In Construction 2.1, when \(j\) is odd and \(j\leq d-2\), it follows from (1) that \(w^j_{HV}(x_{st})\) in diagonal \(D^j\) is always equal to \(2nm+1\). Similarly, it follows from (7) for \(2\leq j+1\leq d-3\) and from (11), (12), and (13) for \(j+1=d-1\) that \(w^{j+1}_{VH}(x_{st})\) is always equal to \(2nm+1\) as well. Therefore, for \(j\) odd, \(1\leq j\leq d-2\) we have \[\begin{aligned} w(x_{st}) &= w^j_{HV}(x_{st}) + w^{j+1}_{VH}(x_{st})\nonumber\\ &=(2nm+1)+(2nm+1)=4nm+2. \end{aligned}\]
For the remaining odd value of \(j=d\) we have diagonal \(D^d\) and the following diagonal is \(D^1\). At the first \(HV\)-corner of \(D^d\) we have from (14) \(w^{d}_{HV}(x_{1(d+1)})=2nm+l\) and from (3) we have \(w^1_{VH}(x_{1(d+1)})=2nm-l+2\) (recall that diagonal \(D^1\) starts at vertex \(x_{1(d+1)}\)). Hence, \[\begin{aligned} w(x_{1(d+1)}) &= w^d_{HV}(x_{1(d+1)}) + w^{1}_{VH}(x_{1(d+1)})\nonumber\\ &=(2nm+l)+(2nm-l+2)=4nm+2. \end{aligned}\]
At the remaining \(HV\)-corners for \(k=2,3,\dots,l\) we have \(w^{d}_{HV}(x_{rs})=2nm\) from (15) and (16) and \(w^1_{VH}(x_{rs})=2nm+2\) from (4). Hence, \[\begin{aligned} w(x_{rs}) &= w^d_{HV}(x_{rs}) + w^{1}_{VH}(x_{rs})\nonumber\\ &=(2nm)+(2nm+2)=4nm+2. \end{aligned}\]
Next we look at weights of vertices that belong to consecutive diagonals \(D^j\) and \(D^{j+1}\) for \(j\) even, \(2\leq j\leq d-3\), provided \(d>3\) and such diagonals exist. The partial weight at the first \(HV\)-corner is \(w^j_{HV}(x_{1(j+1)})=2nm+l\), as follows from (5), while from (3) we have \(w^j_{VH}(x_{1(j+1)})=2nm-l+2\). Therefore, \[\begin{aligned} w(x_{1(j+1)}) &= w^j_{HV}(x_{1(j+1)}) + w^{j+1}_{VH}(x_{1(j+1)})\nonumber\\ &=(2nm+l)+(2nm-l+2)=4nm+2. \end{aligned}\]
For the remaining vertices from (6) we have \(w^j_{HV}(x_{st})=2nm\) and from (4) \(w^{j+1}_{VH}(x_{1(j+1)})=2nm+2\), and \[\begin{aligned} w(x_{st}) &= w^j_{HV}(x_{st}) + w^{j+1}_{VH}(x_{st})\nonumber\\ &=(2nm)+(2nm+2)=4nm+2. \end{aligned}\]
Finally, we examine weights of vertices that belong to diagonals \(D^{d-1}\) and \(D^{d}\). For the \((l'+2)\)-nd \(HV\)-corner, we have \(w^{d-1}_{HV}(x_{st})=2nm+l\) from (9) and \(w^{d}_{VH}(x_{st})=2nm-l+2\) from (19), and \[\begin{aligned} w(x_{st}) &= w^{d-1}_{HV}(x_{st}) + w^{d}_{VH}(x_{st})\nonumber\\ &=(2nm+l)+(2nm-l+2)=4nm+2. \end{aligned}\]
For the remaining vertices we have at \(HV\)-corners \(w^{d-1}_{HV}(x_{st})=2nm\), as follows from (8) and (10), while from (17), (18) and (20) we have \(w^d_{VH}(x_{st)})=2nm+2\). This yields \[\begin{aligned} w(x_{st}) &= w^{d-1}_{HV}(x_{st}) + w^{d}_{VH}(x_{st})\nonumber\\ &=(2nm)+(2nm+2)=4nm+2. \end{aligned}\]
This concludes the case of \(n,m\) both odd, as the weight s of all vertices have been verified.
The case of \(n,m\) even is simpler. In Construction 3.1 when \(j\) is odd, it follows from (21) that \(w^j_{HV}(x_{st})\) in diagonal \(D^j\) is always equal to \(2nm+1\). Similarly, it follows from (26) for \(2\leq j+1\leq d\) that \(w^{j+1}_{VH}(x_{st})\) is always equal to \(2nm+1\) as well. Therefore, for \(j\) odd, \(1\leq j\leq d-1\) we have \[\begin{aligned} w(x_{st}) &= w^j_{HV}(x_{st}) + w^{j+1}_{VH}(x_{st})\nonumber\\ &=(2nm+1)+(2nm+1)=4nm+2. \end{aligned}\]
Finally, we verify the weights of vertices at the seams between \(D^j\) and \(D^{j+1}\) for \(j\) even. This also includes the case when \(j=d\) and \(j+1=1\).
From (24)
it follows that the partial weight at the first \(HV\)-corner is given as
\(w^j_{HV}(x_{1(j+1)})=2nm+l\) and
from (22)
we have the corresponding partial weight
\(w^j_{VH}(x_{1(j+1)})=2nm-l+2\).
Therefore, \[\begin{aligned}
w(x_{1(j+1)}) &= w^j_{HV}(x_{1(j+1)}) +
w^{j+1}_{VH}(x_{1(j+1)})\nonumber\\
&=(2nm+l)+(2nm-l+2)=4nm+2.
\end{aligned}\]
For the remaining vertices we have \(w^j_{HV}(x_{st})=2nm\) from (25) and from (23) we have \(w^{j+1}_{VH}(x_{1(j+1)})=2nm+2\). Hence, \[\begin{aligned} w(x_{st}) &= w^j_{HV}(x_{st}) + w^{j+1}_{VH}(x_{st})=(2nm)+(2nm+2)=4nm+2. \end{aligned}\]
This concludes the case of \(n,m\) both even.
We have now computed weights of all vertices of our graph and concluded that \(w(x_{st})=4nm+2\) for every vertex \(x_{st}\), which completes the proof. ◻
Our result then reduces the original conjecture by Ivančo to the following open problem.
Open Problem 4.3. Does there exist a supermagic labeling of the Cartesian product \(C_n\Box C_m\) for \(n\) odd and \(m\) even or for relatively prime odd numbers \(n,m\)?
We concur with Ivančo that the answer is affirmative. Our belief is supported by the existence of supermagic labelings of \(C_3\Box C_4, C_3\Box C_5\), and \(C_3\Box C_6\) found computationally by Michna [9].