ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 93-107
Group distance magic labeling of direct product of graphs
Martin Anholcer
Poznan University of Economics, Faculty of Informatics and Electronic Economy Al. Niepodleglosci 10, 61-875 Poznan, Poland
Sylwia Cichacz *
AGH University of Science and Technology, Faculty of Applied Mathematics Al. Mickiewicza 30, 30-059 Krakow, Poland
Iztok Peterin, Aleksandra Tepeh
University ofMaribor, Faculty of Electrical Engineering and Computer Science Smetanova 17, 2000 Maribor, Slovenia Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Received 16 January 2013, accepted 28 August 2013, published online 11 July 2014
Let G = (V, E) be a graph and r an Abelian group, both of order n. A group distance magic labeling of G is a bijection I: V ^ r for which there exists m G r such that J2xen(v) Kx) = M for all v G V, where N(v) is the neighborhood of v. In this paper we consider group distance magic labelings of direct product of graphs. We show that if G is an r-regular graph of order n and m = 4 or m = 8 and r is even, then the direct product Cm x G is r-distance magic for every Abelian group of order mn. We also prove that Cm x Cn is Zmn-distance magic if and only if m G {4, 8} or n G {4,8} or m, n = 0 (mod 4). It is also shown that if m, n = 0 (mod 4) then Cm x Cn is not r -distance magic for any Abelian group r of order mn.
Keywords: Abelian group, distance magic labeling, group labeling, direct product of graphs. Math. Subj. Class.: 05C15, 05C22, 05C25, 05C76
*The author was partially supported by National Science Centre grant nr 2011/01/D/ST1/04104. E-mail addresses: m.anholcer@ue.poznan.pl (Marcin Anholcer), cichacz@agh.edu.pl (Sylwia Cichacz), iztok.peterin@um.si (Iztok Peterin), aleksandra.tepeh@um.si (Aleksandra Tepeh)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
94
Ars Math. Contemp. 9 (2015) 93-107
1 Introduction and preliminaries
All graphs considered in this paper are simple finite graphs. We use V(G) for the vertex set and E(G) for the edge set of a graph G. The neighborhood N(x) or more precisely NG(x), when needed, of a vertex x is the set of vertices adjacent to x, and the degree d(x) of x is |N(x) |, the size of the neighborhood of x. By Cn we denote a cycle on n vertices.
We recall two out of four standard graph products (see [8]). Let G and H be two graphs. Both, the Cartesian product GDH and the direct product G x H are graphs with the vertex set V(G) x V(H). Two vertices (g, h) and (g', h') are adjacent in:
•	GDH if g = g' and h is adjacent to h' in H, or h = h' and g is adjacent to g' in G;
•	G x H if g is adjacent to g' in G and h is adjacent to h' in H.
Distance magic labeling (also called sigma labeling) of a graph G = (V(G), E(G)) of order n is a bijection i: V ^ {1,...,n} with the property that there is a positive integer k (called magic constant) such that w(x) = J2yeNa(x) i(y) = k for every x G V(G), where w(x) is the weight of vertex x. If a graph G admits a distance magic labeling, then we say that G is a distance magic graph. See [2] (and also [7]) for the survey on distance magic graphs.
The idea of distance magic labeling of graphs has been motivated by the constructions of magic squares. However, finding an r-regular distance magic graph is equivalent to finding equalized incomplete tournament EIT(n, r) [6]. In an equalized incomplete tournament EIT(n, r) of n teams with r rounds, every team plays exactly r other teams and the total strength of the opponents that team i plays is k.
Some graphs which are distance magic among (some) products can be seen in [1, 3, 4, 5, 9, 10]. Recently a subclass of distance magic graphs was introduced in [1] that behave nicely among products. A distance magic graph G is called balanced if there exists a bijection i: V(G) ^ {1,..., |V(G)|} such that for every w G V(G) the following holds: if u G N(w) with i(u) = i, then there exists v G N(w), v = u, with i(v) = |V(G)| + 1-i. We say that u is the twin vertex of v (and vice versa) and i is called a balanced distance magic labeling. It is easy to see that a balanced distance magic graph has an even number of vertices and that it is an r-regular graph for an even r. Simple examples are empty graph on an even number of vertices, cycle C4, and K2n - M, for a perfect matching M. The following theorem was proved in [1] and will be used in the second section.
Theorem 1.1 ([1]). The direct product G x H is a balanced distance magic graph if and only if one of the graphs is balanced distance magic and the other one is regular.
Group distance magic labeling of graphs was recently introduced by Froncek in [5] as in some sense a generalization of distance magic labeling. Let r be a finite Abelian group of order n. A r-distance magic labeling of a graph G with |V(G)| = n is an injection from V to r such that the weight of every vertex x G V is equal to the same element ^ G r, called the magic constant. If there exists a r-distance magic labeling of G, we say that G is a r-distance magic graph. A graph G is called a group distance magic graph if there exists a r-distance magic labeling for every Abelian group r of order |V(G)|. The connection between distance magic graphs and r-distance magic graphs is as follows. Let
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
95
G be a distance magic graph of order n. If we replace n in {1,..., n} by 0, we obtain a Zn-distance magic labeling. Hence every distance magic graph is a Zn-distance magic graph. The question remains what happens when we replace Zn by some other Abelian group, and which graphs are r-distance magic but not distance magic. The following theorem was proved in [5]:
Theorem 1.2 ([5]). The Cartesian product CmUCk, m, k > 3, is a Zmk-distance magic graph if and only if km is even.
Froncek also showed that the graph C2kdC2k has a (Z2)2k-distance magic labeling for k > 2 and ^ = (0,0,..., 0) ([5]).
It seems that the direct product is the natural choice among (standard) products to deal with r-distance magic graphs and group distance magic graphs in general. The reason for this is that the direct product is suitable product if we observe graphs as categories. Hence it should perform well with the product of (Abelian) groups. The confirmation of this will be illustrated in the first theorem of each forthcoming section. This fact also makes the direct product the most natural among graph products, but on the other hand the most difficult to handle. Namely, G x H does not need to be connected, even if both factors are. More precisely, G x H is connected if and only if both G and H are connected and at least one of them is non-bipartite [11]. The direct product is commutative, associative, and has attracted a lot of attention in the research community in last 50 years. Probably the biggest challenge (among all products) is the famous Hedetniemi's conjecture:
x(G x H)=min{x(G),x(H)}.
This conjecture suggests that the chromatic number of the direct product depends only on the properties of one factor and not both. This is not so rare and also in this work we show that it is enough for one factor to be a balanced distance magic graph and then the direct product with any regular graph will result in a group distance magic graph. For more about the direct product and products in general we recommend the book [8].
For V(G) = {xo, xi,..., x|y(G)|-i} and V(H) = {yo, yi,..., y|y(H)|-i} we use
V(G x H) = {vij : i e {0,1,..., |V(G)| - 1}, j e {0,1,..., |V(H)| - 1}}.
The fundamental theorem of finite Abelian groups states that the finite Abelian group r of order n can be expressed as the direct sum of cyclic subgroups of prime-power order. This implies that r = Zp«i x ... x Zpmm, where n = f]™1 pf* andp for i e {1,..., m} are not necessarily distinct primes. In particular, if n = 0 (mod 4), then we have the following possibilities: r = Z2 x Z2 x Zpai x ... x Zpmm and n — 4 i=i pai or r = Z4 x Z^i x ... x Zpmm and n = 4 f]m=1 P?i or r = Z2ao x Zp^i x ... x Zpmm and n = 2ao f]™ 1 pT, a0 > 3. This fact will be used often in what follows. Recall that any group element g e r of order 2 (i.e., g = 0, 2g = 0) is called an involution, and that a non-trivial finite group has elements of order 2 if and only if the order of the group is even. Moreover every cyclic group of even order has exactly one involution. We will use the notation a0 for the identity element of an Abelian group A.
In the next section we present some general results about group distance magic label-ings on the direct products. In the last section we concentrate on direct product of cycles. We will prove also that a graph Cm x Cn is Zmn-distance magic if and only if m e {4,8} or n e {4,8} or m, n = 0 (mod 4). Moreover, we will show that if m, n = 0 (mod 4) then Cm x Cn is not r-distance magic for any Abelian group r of order mn.
96
Ars Math. Contemp. 9 (2015) 93-107
2 General results
We start with the following general theorem for direct product of graphs:
Observation 2.1. If an ri-regular graph G1 is ^-distance magic and an r2 -regular graph G2 is r2-distance magic, then the direct product G1 x G2 is r1 x r2-distance magic.
Proof. Let ^: V(Gj) ^ r be a rrdistance magic labeling, and m the magic constant for the graph Gj, i e {1,2}. Define the labeling I: V(G1 x G2) ^ r1 x r2 for G1 x G2, as:
¿((x,y)) = (4 (x),^2(y)). Obviously, I is a bijection and moreover, for any (u, w) e V(G1 x G2):
w(u,w) = 53 ^(x,y)= I r2 ^1(x),r1 ^(y) I ,
(x,y)eNa1xa2 (u,w)	\ xeNGl (u)	y£NG2 (w) J
w(u,w) = (r2^1,r1 M2) = M,
which settles the proof.	□
Theorem 2.2. If G is a balanced distance magic graph, then G is a group distance magic graph.
Proof. Let G be a balanced distance magic graph of order n. Recall that n is an even number and G is an r-regular graph for an even r. For any Abelian group r of order n holds r = Z2t xA for some natural number t > 0 and some Abelian group A of order 2f .If g e r, then we can write g = (j, aj) where j e Z2t and aj e A for i e {0,1,..., 2nt - 1}. Let V (G) = {u1, u2,..., u n, u1, u2,..., u'n }. For i e {1,..., f} we define the following labeling I for a vertex uj and its twin vertex uj:
¿(u) = ((i - 1)(modt),aLi-i^ and ¿(uj) = (2t - 1,a0) - ¿(u). Since ¿(u) + ¿(uj) = (2t - 1, a0) for every i e {1,..., f }, we get
w(v) = £ ¿(u)= £ (¿(u) + ¿(uj)) =
u£N (v)	UiEN(v)
= £ (2t - 1,ao) = 2(2t - 1,ao),
UiEN (v)
where § is an integer since r is even. Moreover, every element of r is used exactly once and so G is r-distance magic.	□
Since for any graph G of order m, the graph Kn x G is isomorphic to Knm, by Theorems 1.1 and 2.2 the next result immediately follows.
Theorem 2.3. If G is a balanced distance magic graph and H an r-regular graph for r > 1, then G x H is a group distance magic graph.	□
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
97
Notice that by the above Theorem 2.3, if G is an r-regular graph (r > 1), then the graph C4 x G is a group distance magic graph. We cannot generalize this result to other cycles than C4. Namely, Cn x K2 is isomorphic to 2Cn (i.e., the union of two cycles Cn) when n is even and to C2n when n is odd. It is easy to see that both 2Cn for n = 4 and C2n for n = 2 are not r- distance magic for any Abelian group r of order 2n (for n > 5, in both cases under the assumption that there is some group distance magic labeling we obtain ^(vj) = ¿(vi+4) for all the vertices vj, and we easily derive a contradiction also for n = 3). Nevertheless, for many regular graphs the result still holds. For C8 as we will see next.
Theorem 2.4. If G is an r-regular graph of order n for some even r, then direct product C8 x G is a group distance magic graph.
Proof. Let V(G) = {xo, xi,..., xn-i} be the vertex set of G, let C8 = woui... uruo, and H = C8 x G. Notice that if xpxq G E(G), then vj,q G (vijP) if and only if j G {i - 1, i + 1} (where the sum on the first suffix is taken modulo 8). We are going to consider three cases, depending on the structure of r.
Case 1: r = Z2 x Z2 xA for some Abelian group of order 2n.
We can write g G r as j j2, ak) for j^ j2 G Z2 and ak G A for k e {0,1,..., 2n -1}. For j G {0,1,..., n - 1} we set
( (0,0,a2j+j),	if i G {0,1},
^Kj) = { (0,1,a2j+i-4),	if i G {4, 5},
[ (1,1,ao) - ^(vj_2,j), if i G{2, 3, 6, 7}.
Clearly, I : V(C8 x G) ^ r is a bijection and ¿(vitj) + ^(vi+2j) = (y,a0), where yi G {(1,1), (1,0)}, and so 2yi = (0,0). Hence for every i G {0,1,..., 7} and j G {0, 1, . . . , n - 1} we get
w(vj,j) = £ (^(vi-i,p) + ^(vi + i,p)) = £ (Vi-i,ao) =
xpeNa(xj)	xpeNa(xj)
r
= 2(0, 0,ao) = (0, 0,ao)
and C8 x G is r-distance magic since r is even.
Case 2: r = Z4 xA for some Abelian group A of order 2n.
If g G r, then we can write g = (j, ak) for j G Z4 and ak G A for k G {0,1,..., 2n -1 }. For j G { 0, 1 , . . . , n - 1 } we define
( (0,a2j+i),	if i G{0, 1},
£(vi,j)= { (2,a2j+i-4),	if i G {4, 5},
[ (3,ao) - l(vi-2,j), if i G{2, 3, 6, 7}.
Again I: V (C8 x G) ^ r is obviously a bijection and ^(viij- )+^(vi+2,j) = (yi, ao), where yi G {1, 3}, and thus 2yi = 2. Hence for every i G {0,1,..., 7} and j G {0,1,..., n - 1} we get
w(vi,j) = £ (^(vi-i,p)+ %i+i,p))= £ (Vi-i,ao) = 2 (2,ao) = (r,ao)
Xp£NG(xj)	XpENG (xj)
98
Ars Math. Contemp. 9 (2015) 93-107

and C8 x G is r-distance magic.
Case 3: r = Z2a xA for a > 2 and some Abelian group A of order .
If g e r, we can write g = (p, ak) for p e Z2a and ak 6 A for k G {0,1,..., 1}. For j g {0,1,..., 50-3 - 1} define the following labeling
( ((2j + i)(mod2a-2), a j.2-a+3j) , if i G {0,1}, ¿(vij) = < (2a-1, ao) +	) ,	if i G {4, 5},
[ (2a - 1, ao) - ¿(v^j),	if i G{2, 3, 6, 7}.
As in previous cases I : V(C8 x G) ^ r is a bijection and ¿(vj,j) + ¿(vi+2,j) = a0) for some y G {2a-1 - 1, 2a - 1}. Thus 2(*(vi,j) + ¿(vi+2,j)) = (2y<, ao) = (-2, ao). For every i G {0,1,..., 7} and j G {0,1,..., n - 1} we get
w(vi,j) =	(¿(vi-i,p) + ¿(vi+i,p)) =	(yi-i,ao) =
xpeNa(xj)	xpeNa(xj)
r
= 2(-2, ao) = (-r, ao) and C8 x G is Z2a xA-distance magic.	□
The natural question arises whether we can prove similar results for every cycle Cn where n = 0 (mod 4). The answer to this question is negative as we will see in the next section. It will also be clear from the following section why we cannot expect similar results for n = 0 (mod4). (For both claims see Theorem 3.5.) However, below we give some groups r such that for G being an r-regular graph of order n for some even r, the direct product C2p x G admits a r-distance magic labeling.
Proposition 2.5. If G is an r-regular graph of order n for some even r, then the direct product C2p x G, p > 2, admits an Ax B-distance magic labeling for any Abelian group B of order n and an Abelian group A such that:
•	A = (Z2)p,
•	A = Z4 x(Z2)p-2,
•	A = Z8 x(Z2)p-3,
•	A= (Z4)2 x (Z2)p-4.
Proof. Let V(G) = {xo, x1,..., xn-1} be the vertex set of G, let C2p = wou1... u2p-1uo, and H = C2p x G. Notice that if xpxq G E(G), then vj,q G NH(v»,p) if and only if j G {i - 1, i + 1} (where the sum on the first suffix is taken modulo 2p). Let the elements of B be bo, b1,..., bn-1. Recall that for any element r e (Z2)p we have 2r = 0.
Case 1: A = (Z2)p. Let the elements of (Z2)p be ro,..., r2p-1. Each element of r = (Z2)p x B can be thus expressed as (r, bj), where r e (Z2)p and bj e B. We define the labeling I as follows:
i (ri,bj), if i(mod4) G {0,1},
¿(Vi,j) = \ (ri, -bj), if i(mod4) G {2, 3}.
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
99
It is straightforward to check that i is bijective and i(v ,j)+ i(vj+2,j) = (r + rj+2, bo). Hence for every i G {0,1,..., 2p - 1} and j G {0,1,..., n - 1} we get
w(vj,j) =	(i(vi-i,d) + i(vj+i,d)) = ^ (rj-i + ri+i,bo) =
XdeNa(xj)	XdeNa(xj)
r
= 2(ro, bo) = (ro, bo)
and C2p x G is (Z2)p x B-distance magic since r is even.
Case2: A = Z4 x(Z2)p-2. Let the elements of (Z2)p-2 be ro,..., r2p-2-1. Each element of r = Z4 x (Z2)p-2 x B can be thus expressed as (q, r, bj), where q G Z4, r G (Z2)p-2, and bj gB. We define the labeling i in the following way
i(v ) i (q,rj,bj), if q G {0, 1}, i(v4j+q,j) | (q,rj, -bj), if q g {2, 3}.
Again it is easy to check that i is bijective and i(vj,j) + i(vj+2,j) = (yj, zj, bo), where Vi G {0,2} and Zj = r^j + rL(j+2)/4j, and so 2(vj,Zj) = (0,ro). Hence for every i G {0,1,..., 2p - 1} and j G {0,1,..., n - 1} we get
w(vj,j) =	(i(vj-i,d)+ i(vj+i,d)) =	(Vi-i, Zj-i, bo) =
xdeNa(xj)	xdeNa(j)
r
= 2 (0, ro, bo) = (0, ro, bo)
and C2p x G is Z4 x (Z2)p-2 x B-distance magic since r is even.
Case 3: A = Z8 x(Z2)p-3. Let the elements of (Z2)p-3 be ro,..., r2p-3-i. Each element of r = Z8 x(Z2)p-3 x B can be thus expressed as (a(q),rj,bj), where q G Z8, rj G (Z2)p-3, bj G B, and the function a : Z8 ^ Z8 is defined as a(2) = 3, a(3) = 2, a(6) = 7, a(7) = 6, and a(j) = j for remaining j G Z8. We define the labeling i in the following way.
f (a(q),rj,bj), if q(mod4) G {0, 1}, i(v8j+q,j	(a(q),rj, -bj), if q(mod4) G {2, 3}.
It is easy to see that i is bijective and i(vj,j) + i(vj+2,j) = (yj, zj, bo), where (yj, zj) G {(3, 2rLj/8j), (7,rLj/8j+rL(j+2)/8j)}, so 2(vj,Zj) = (6, ro). Hence for every i G {0,1,..., 2p - 1} and j G {0,1,..., n - 1} we get
w(vj,j)= ^ (i(vj-i,d) + i(vj+i,d)) =	(Vj-i, Zj-i, bo) = 2(6, ro,bo)
Xd£NG(xj)	Xd£NG(xj)
and C2p x G is Z8 x (Z2 )p-3 x B-distance magic since r is even.
Case 4: A = (Z4)2 x (Z2F-4. Let the elements of (Z2F-4 be ro,..., r2p-4-i. Each element of r = (Z4)2 x (Z2)p-4 x B can be thus expressed as (a(q), rj, bj), where q G Zi6, rj G (Z2)p-4, bj- G B, and the function a : Zi6 ^ (Z4)2 is defined as
100
Ars Math. Contemp. 9 (2015) 93-107
i	0	1	2	3	4	5	6	7
o(i)	(0,0)	(0,3)	(1,1)	(1,2)	(2,2)	(2,1)	(3,3)	(3,0)
i	8	9	10	11	12	13	14	15
o(i)	(0,2)	(0,1)	(1,3)	(1,0)	(2,0)	(2,3)	(3,1)	(3,2)
We define the labeling i in the following way:
f (a(q),ri,6j), if q(mod4) G {0, 1}, i(Vi6i+q'j) \ (a(q),ri, -bj), if q(mod4) G {2, 3}.
It is easy to see that i is bijective and i^j) + i(vi+2jj) = (%, Zj, b0), where y G {(1,1), (1, 3), (3,1), (3, 3)} and Zj = rLiA6j + rL(i+2)/i6j, so 2(y<, Zj) = (2, 2, ro). Hence for every i G {0,1,..., 2p - 1} and j G {0,1,..., n - 1} we get
w(vj,j) =	(i(vj-i,d) + i(vi+M)) =	(yj_i,Zj_i,bo) = 2(2, 2, ro,bo)
XdeNa(xj)	XdeNa(xj)
and C2p x G is (Z4)2 x (Z2)p 4 x B-distance magic since r is even.	□
Proposition 2.6. If G is an r-regular graph of order n for some even r and n, then the direct product C2P x G, p > 2, admits an Ax B-distance magic labeling for any Abelian group B of order n and an Abelian group A such that:
•	A = Z8 x Z4 x(Z2)p-4,
•	A = Zi6 x(Z2)p-3.
Proof. Let V(G) = {x0, xi,..., xn-i} be the vertex set of G, let C2p = w0ui... u2p_iu0, and H = C2p x G. Notice that if xpxq G E(G), then vj,q G (vjjp) if and only if j G {i - 1, i + 1} (where the sum on the first suffix is taken modulo 2p). Let the elements of B be b0, bi,..., bn/2-i.
Case 1: A = Z8 x Z4 x(Z2)p-4. Each element of r = Z8 x Z4 x(Z2)p-4 x B can be expressed as (a(q),rj,bj), where q G Z32, r G (Z2)p-4, bj G B, and the function 0 : Z32 ^ Z8 x Z4 is defined as:
i	0	1	2	3	4	5	6	7
o(i)	(0,0)	(1,0)	(3,1)	(2,1)	(4,2)	(5,2)	(7,3)	(6,3)
i	8	9	10	11	12	13	14	15
o(i)	(0,2)	(1,2)	(3,3)	(2,3)	(4,0)	(5,0)	(7,1)	(6,1)
i	16	17	18	19	20	21	22	23
o(i)	(0,3)	(1,3)	(3,2)	(2,2)	(4,1)	(5,1)	(7,0)	(6,0)
i	24	25	26	27	28	29	30	31
o(i)	(0,1)	(1,1)	(3,0)	(2,0)	(4,3)	(5,3)	(7,2)	(6,2)
For j = 0 (mod 2) we define the labeling i in the following way:
i(vi6i+t,j ) =
(a(t),rj,bLjj), if t(mod4) G {0,1},
(o(t),rj, -bL jj), if t(mod4) G {2, 3};
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
101
and for j = 1 (mod 2) we set i(vi6j+t,j ) =
(a(16 + t),rj,6L j j), if t(mod4) G {0,1}, (a(16 + t), rj, — b L j j), if t(mod4) G {2, 3}.
It is straightforward to check that i is bijective and i(vjjj) + i(vj+2,j) = (y, zj, bo), where yi G {(3,1), (7, 3), (7,1)} and Zj = ^¿/^j + rL(i+2)/i6j+i, so 2(yj,Zj) = (6, 2,ro). Hence for every i G {0,1,..., 2p — 1} and j G {0,1,..., n — 1} we get
w(vj,j) =	(i(vj-i,d) + i(vj+i,d)) =	(yi-i,Zj-i,bo) = 2(6, 2,ro,bo)
Xd&Na(xj)	xdeNa(xj)
and C2p x G is Z8 x Z4 x (Z2 )p-4 x B-distance magic since r is even.
Case 2: A = Zi6 x(Z2)p-3. Each element of r = Zi6 x(Z2)p-3 xB as (a(q),rj,bj), where q G Zi6, ri G (Z2)p-3, bj G B, and the function a : Zi6 ^ Zi6 is defined as:
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a(i)	0	2	1	15	8	10	9	7	4	6	13	11	12	14	5	3
We define the labeling i for j = 0 (mod 2) as
' (a(t),rj,bLjj), if t(mod4) G {0, 1},
i(v8j+t,j ) = and for j = 1 (mod 2) by
(a(t),rj, —bL jj), if t(mod4) G {2, 3},
(a(8 + t),rj,bLjj), if t(mod4) G {0, 1}, (a(8 + t),ri, —jj), if t(mod4) G {2, 3}.
i(v8i+t,j ) = ^ --------- L 2 j
Again it is easy to see that i is bijective and i(vi,j) + i(vj+2,j) = (yi,zi,bo), where yi G {1,9} and Zj = rLi/8j + ^+2)^, so 2(yj,Zj) = (2,ro). Hence for every i G {0,1,..., 2p — 1} and j G {0,1,..., n — 1} we get
w(vj,j)=	(i(vj-i,d) + i(vi+i,d)) =	(yj-i, Zj-i, bo) = ^(2, ro,bo)
Xd£Na(xj)	XdENa(xj)
and C2p x G is Zi6 x (Z2)p 3 x B-distance magic since r is even.	□
3 r-distance magic labeling of Cm x Cn
In this section we concentrate on the direct product of two cycles.
Theorem 3.1. If m, n = 0 (mod 4), then the direct product Cm x Cn is Ax B-distance magic for any Abelian groups A and B of order m and n, respectively.
Proof. Let r = A x B and let bo be the identity of B. We consider three cases, depending on the factorization of r.
102
Ars Math. Contemp. 9 (2015) 93-107
Case 1: r = Z2 x Z2 xGxB for some Abelian group G of order f.
If g G r, then we can write g = (ji,j2,ak, bj) for ji,j2 G Z2, ak € G for k G {0,1,..., f - 1}, and bj G B for j G {0,1,..., n - 1}. For i G {0,1,..., m - 1} we set:
¿(v .) = f ^i^^j	if i(mod4) G {0,1},
(1,1,ao,bo) - i(vi-2,j), if i(mod4) G {2, 3}, for j(mod4) G {0, 1} and
. )= f (0,i -aL j j, bj),	if i(mod4) G{0,1},
( i,j) 1(1,1,ao,bo) - ¿(vi-2,3), if i(mod4) G {2, 3},
for j(mod4) G {2, 3}.
It is easy to see that ¿ : V(Cm x Cn) ^ r is a bijection and w(vj,j) = ^(vi_1,j-_1) + ¿(vi_i,j+i) + ¿(vi+i,j_i) + ¿(vi+i,j+i) = (0, 0, ao, bo).
Case 2: r = Z4 xG x B for some Abelian group G of order f.
If g G r, then we can write g = (q, ak, bj) for q G Z4, ak G G for k G {0,1,..., f -1}, and bj G B for j G {0,1,..., n - 1}. For i G {0,..., m - 1} we define the following labeling ¿:
¿Kj) = {
for j(mod4) G {0,1} and
(i, aLij, bj),	if i(mod4) G {0,1},
(3, ao* bo) - ¿(vi_2,j), if i(mod4) G {2, 3},
_	) | (i, -aLjj,bj),	if i(mod4) G{0, 1}
( i,j) \ (3,ao,bo) - ¿(vi_2,j), if i(mod4) G {2, 3},
for j(mod4) G {2, 3}.
Again ¿: V(Cm x Cn) ^ r is a bijection and w(v4,j) = ¿(vi_i,j_i) + ¿(vi_i,j+i) + ¿(vi+i,j_i) + ¿(vi+i,j+i) = (2, ao, bo).
Case 3: r = Z2a xG x B for a > 2 and some Abelian group G of order f.
Notice that this case is meaningful only when m = 0 (mod 8). If g G r, then we can write that g = (q, ak, bj) for q G Z2a, ak G G for k G {0,1,..., 2f - 1} and bj G B for j G {0,1,..., n - 1}. For i G {0,..., m - 1} we define the following labeling ¿:
((i(mod2a))2a_2, aLi/2aj,bj) ,	if i(mod2a) G {0,1},
2a))2a_2,
¿Kj' )={ ((1 - i(mod2a))2a_2, -aLi/2aj, -b^ , if i(mod2a) G {2, 3},
(1,ao,bo) + ¿(vi_4,j),	if i(mod 2a) £ {0,1, 2, 3},
for j(mod4) G {0, 1} and
( (-(i(mod 2a))2a_2 - 1, -aLi/2aJ, -bj-) , if i(mod2a) G {0,1},
¿(vi,j )=< ((i(mod 2a - 1))2a_2 - 1,aLi/2aj,bj) ,	if i(mod2a) G {2, 3},
[ (-1,ao,bo) + ¿(vi_4,j),	if i(mod 2a) G {0,1, 2, 3},
for j(mod4) G {2, 3}.
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
103
It is easy to see that £ : V(Cm x Cn) ^ r is a bijection and moreover, ) =
£(vi-i,j-i) + £(vi+i j-i) + £(«¿-1,^+1) + £(vi+ij+i) = ( - 2, ao, 60).	□
One can ask if it is possible to find an AxB -distance magic labeling of Cm x Cn, if |A| > m. A partial answer is given by the following observation.
Proposition 3.2. If m,n = 0 (mod 4), then the direct product Cm x Cn is Zt xA -distance magic for m|t and any Abelian group A order .
Proof. Let r = Zt xA where m|t and A is an Abelian group of order mp. If g € r, then we can write that g = (j, ak) for j € Zt and ak € A for k € {0,1,..., mr - 1}. For
i € {0,1,..., m - 1} let
jm(mod t) 2 , jm(mod t)
i< L jm j
£(vi,j)
for j(mod4) € {0,1} and
£(«¿,5) = <

2 1 4
jm(mod t)
l j
-m ,-a
4
l jm j.
jm(mod t) 2
2 , aLjrj
£(«¿-4,5 ) + (1, ao),
jm(mod t) , a
2	1, aL ^j

jm(mod t) m i
2	T - 1, -aLjmj
jm(mod t) . m i -T--r li--1,
jm(mod t) | m i „
2 + 2 1, aL^j
L jm j,
£(vi-4,j ) + (-1,ao),
if	i = 0
if	i = 1
if	i = 2
if	i = 3
if	i > 3,
if i = 0 , if i = 1
if i = 2
if i = 3 if i > 3,
for j(mod4) € {2, 3}.
Notice that we obtain mn/t blocks such that in every block we have all elements from Zt as the first coordinate. Moreover for i € {0,1,..., mn/t - 1} in i-th block we have labels (j, ai), where j € {0,1,..., t/2 - 1}. Therefore £ is bijective and ^ = (-2, a0) is the magic constant.	□
The above results encourage us to post the following conjecture.
Conjecture 3.3. If m, n = 0 (mod 4), then Cm x Cn is a group distance magic graph.
Now we are going to present some sufficient conditions for a graph G not to be group distance magic.
Theorem 3.4. Assume that m, n > 3, m, n € {4,8}, m = 46 + d and n = 4a + c for some integers a, 6 > 0 where c € {0,1, 2, 3} and d € {1,2, 3}. If an Abelian group r of order mn has less than max{2, a - 1} involutions, then Cm x Cn is not T-distance magic.
Proof. Let m, n, a, 6, c, d be as in the statement of the theorem. Thus m = 0 (mod 4). Let G = Cm x Cn. Assume that there exists a group r of order mn such that G is T-distance magic, i.e., there is a bijection £ : V(G) ^ r such that for every x € V(G), w(x) = ^ for some constant ^ € r. Furthermore, let g0 be the identity of r.
2
104
Ars Math. Contemp. 9 (2015) 93-107
For any integers i, p, and s we have
w(vi+p+i,s+i) =	+ ^(vi+p,s+2) + ^(vi+p+2,s) + ^(vi+p+2,s+2) = M,
where the first suffix is taken modulo m, and the second one modulo n. Comparing the above equality for p = 0 and p = 2, we obtain
) + ^(vi,s+2) = ^(vi+4,s) + ^(vi+4,s+2).
More generally, if we consider the equality for p = j and p = j + 2 for some integer j, we obtain that
^(vi+j>) + ^(vi+j,s+2) = ^(vi+j+4,s) + ^(vi+j+4,s+2) for every j. In consequence,
+ ^(Vj,s+2) = ^(vi+4j,s ) + ^(vi+4j>+2)	(3.1)
for every j .As m ^ 0 (mod 4), there exists such a j that i + 4 j = i + 2 (mod m). This way we obtain from (3.1)
) + ^(vi,s+2) = ^(vi+2,s) + ^(vi+2,s+2).	(3.2) Substituting s with s + 2 in (3.2) we obtain
^(Vj,s+2) + ^(Vj,s+4) = ^(vi+2,s+2) + ^(vi+2,s+4)	(3.3) and finally by subtracting (3.3) from (3.2)
) - ^(vi,s+4) = ^(vi+2,s) - ^(vi+2,s+4).	(3.4) In a similar way as (3.1) we can prove that for any i, j, and s
+ ^(vi+2,s) = ^(vi,s+4j ) + ^(vi+2,s+4j ).	(3.5) In particular from (3.5) for j = 1 we get
) - ^(vi,s+4) = ^(vi+2,s+4) - ¿(vi+2,s).	(3.6) This leads, if we add together (3.4) and (3.6), to
2(^(vj,s) - ^(vj,s+4)) = go.
By comparing the last equality for s = 4p and s = 4(p + 1), where p is any nonnegative integer, we can observe that
2(^(vj,o) - ^(vj,4p)) = go
at least for every 1 < p < a - 1. This bound is sharp when c = 0. Let first a > 2. We have at least
2(^Ko) - ¿(vi,4)) = go and 2(^(v4,o) - ¿K,s)) = go.	(3.7)
On the other hand, if a < 2, then c = 0, since n {4,8}. Hence vj,o, vj,4, and vj,g are again different vertices and (3.7) holds as well.
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
105
Fix i = 0. Since £ is bijection, £(vo,o) - £(vo,4p) = 0 for every p such that p G {1,..., a-1}, therefore £(v0,0)-£(v0,4p) has to be an involution for every p G {1,..., a -1} and we have at least two involutions when n = 3. Moreover, bijectivity of £ implies that
£(vo,o) - £(vo,4pi) = £(vo,o) - £(vo,4p2)
for every pi = p2 such that pi,p2 G {1,..., a - 1}. Thus the set of involutions of r has to consists of at least max{2, a - 1} distinct elements.	□
Theorem 3.5. If m, n ^ 0 (mod 4) then Cm x Cn is not T-distance magic for any Abelian group r of order mn.
Proof. If m, n are odd, then any group r has odd order mn and we are done by Theorem 3.4, as there are no involutions in r. If m = 2 (mod 4) and n is odd (or n = 2 (mod 4) and m is odd, resp.), then mn = 2 (mod 4). Thus by the fundamental theorem
of finite Abelian groups r = Z2 x Z„«i x ... x Z„«fc where mn = 2 f]i=1 p"i and p» > 2
p 1 pk
for i G {1,..., k} are not necessarily distinct primes. Therefore there exists exactly one involution i in r (i = (1,0,..., 0)) and we are done by Theorem 3.4.
Suppose now that m, n = 2 (mod 4), then m = 2 + 4a, n = 2 + 4b and mn = 4(1 + 2a)(1 + 2b) for some integers a, b. Thus by the fundamental theorem of finite Abelian groups r = Z2 x Z2 x A or r = Z4 x A for some Abelian group A of order (1 + 2a)(1 + 2b). Since (1 + 2a)(1 + 2b) is an odd number, then, if r = Z4 x A, there exists only one involution i = (2,0) in r and Cm x Cn is not Z4 x A-distance magic by Theorem 3.4.
In the case r = Z2 x Z2 x A, there exist exactly three involutions i1 = (1,0,0), i2 = (0,1,0) and i3 = (1,1,0) in r. Let G = Cm x Cn and assume that G is T-distance magic, i.e., there is a bijection £ : V(G) ^ r such that for every x G V(G), w(x) = m for some constant m. Using the same arguments as in the proof of Theorem 3.4, since
m = 2 (mod4), we obtain that 2(£(vo,o) + £(vo,2)) = 2(£(vo,2) + £(vo,4)) = M and 2(£(vo,4) + £(vo,6)) = 2(£(vo,6) + £(vo,g)) = M. On the other hand since n = 2 (mod4) we have gcd(2, n) = gcd(4, n) = 2 and there exists a' such that 4a' = 2 (modn). By repeating the above arguments we get 2(£(vo,4) + £(v2,4)) = 2(£(v2,4) + £(v4,4)) = m and 2(£(vo,4) + £(vm-2,4)) = 2(£(vm_2,4) + £(vm-4,4)) = M. Therefore:
2(£(vo,o) - £(vo,4)) = 2gi = 0, 2(£(vo,s) - £(vo,4)) = 2g2 = 0, 2(£(V4,4) - £(vo,4)) = 2g3 = 0 2(£(vm_4,4) - £(vo,4))=2g4 = 0.
If any g =0 (for i G {1, 2,3,4}), then the labeling £ is not a bijection as m, n ^ 0 (mod 4). Thus we can assume that all g are involutions and by the Pigeonhole Principle there exist j = i such that g = gj (since there are only three involutions in r) what implies that the labeling £ is not a bijection m, n ^ 0 (mod 4) (e.g., if g2 = then
£(vo,8) = £(vo,4)), a contradiction.	□
The immediate corollary follows.
Corollary 3.6. Assume that m, n > 3 and {m, n} = {4a, 4b + c} for some integers a > 3 and b > 0, c G {1, 2, 3}. Then Cm x Cn can be T-distance magic only in the following cases:
106
Ars Math. Contemp. 9 (2015) 93-107
•	c g {1, 3} and r = Ax (Z2)p+2 for some Abelian group A of odd order, where
a = 2p,
•	c G {1, 3} and r = Ax Z3 x (Z2)p for some Abelian group A of odd order, where
a = 3 • 2p-2,
•	c G {1,3} and r = A x (Z2)p x Z4 for some Abelian group A of odd order, where
a = 2p,
•	c G {1, 3} and r = Ax (Z2)p-2 x (Z4)2 for some Abelian group A of odd order, where a = 2p,
•	c G {1,3} and r = Ax (Z2)p-1 x Z8 for some Abelian group A of odd order, where a = 2p,
•	c =2 and r = A x (Z2 )p+3 for some Abelian group A of odd order, where a = 2p,
•	c =2 and r = Ax Z3 x (Z2)p+1 for some Abelian group A of odd order, where
a = 3 • 2p-2,
•	c = 2 and r = A x Z3 x(Z2)p-1 x Z4 for some Abelian group A of odd order, where a = 3 • 2p-2,
•	c =2 and r = Ax Z5 x (Z2 )p for some Abelian group A of odd order, where
a = 5 • 2p-3,
•	c =2 and r = Ax Z7 x (Z2 )p for some Abelian group A of odd order, where
a = 7 • 2p-3,
•	c =2 and r = Ax (Z2)p+1 x Z4 for some Abelian group A of odd order, where
a = 2p,
•	c =2 and r = A x (Z2)p-1 x (Z4)2 for some Abelian group A of odd order, where
a = 2p,
•	c = 2 and r = A x (Z2)p x Z8 for some Abelian group A of odd order, where
a = 2p,
•	c =2 and r = Ax (Z2)p-2 x Z4 x Z8 for some Abelian group A of odd order, where a = 2p,
•	c = 2 and r = Ax (Z2)p-1 x Z16 for some Abelian group A of odd order, where
a = 2p.
Proof. Let a = a2p for some odd number a. Observe that the number of involutions is equal to 2^ - 1, where fi is the number of the factors Z2k of r. By Theorem 3.4 we have a2p - 1 < 2^ - 1 and hence a < It is straightforward to see that if c G {1,3}, then the maximum number of such factors is p + 2 and a < 4, while in the case when c =2
it is p + 3 and a < 8. Moreover Ze = Z3 x Z2, Z10 = Z5 x Z2, Z12 = Z4 x Z3 and Z14 = Z7 x Z2 are the only groups of the respective order, so the listed groups are the only ones that consist of at least p factors Z2 k.	□
In the previous section in Propositions 2.5 and 2.6 we presented constructions for all the cases from Corollary 3.6, where m = 2p or n = 2p for some integer p. However we think that whole Corollary 3.6 gives not only necessary but also sufficient conditions for a graph to be group distance magic so we post the following conjecture.
M. Anholcer et al.: Group distance magic labeling of direct product of graphs
107
Conjecture 3.7. Assume that m, n > 3 and {m, n} = {4a, 4b + c} for some integers a > 3 and b > 0, c G {1,2,3}. Then Cm x Cn is T-distance magic in the following cases:
•	c G {1,3} and r = Ax Z3 x (Z2)p for some Abelian group A of odd order, where
a = 3 • 2p-2,
•	c =2 and r = Ax Z3 x (Z2)p+1 for some Abelian group A of odd order, where
a = 3 • 2p-2,
•	c = 2 and r = A x Z3 x(Z2 )p-1 x Z4 for some Abelian group A of odd order, where a = 3 • 2p-2,
•	c =2 and r = Ax Z5 x(Z2)p for some Abelian group A of odd order, where
a = 5 • 2p-3,
•	c =2 and r = Ax Z7 x(Z2)p for some Abelian group A of odd order, where
a = 7 • 2p-3,
We finish with the following result.
Theorem 3.8. A graph Cm x Cn is Zmn-distance magic if and only if m G {4,8} or
n G {4, 8} or m,n = 0 (mod4).
Proof. If m = 0 (mod 4) and n G {4, 8}, or n = 0 (mod 4) and m G {4,8}, then the group Zmn has at most one involution i (namely i = mp, if mn is even) and so Cm x Cn is not Zmn-distance magic by Theorem 3.4. If n = 4 or m = 4 then Cm x Cn is Zmn-distance magic by Theorem 2.3 and if m, n = 0(mod4), then Cm x Cn is Zmn-distance magic by Proposition 3.2. If n = 8 or m = 8, then the graph Cm x Cn is Zmn-distance magic by Theorem 2.4.	□
References
[1]	M. Anholcer, S. Cichacz, I. Peterin, A. Tepeh, Distance magic labeling and two products of graphs, Graphs Combin., accepted.
[2]	S. Arumugam, D. Froncek and N. Kamatchi, Distance Magic Graphs - A Survey, Journal of the Indonesian Mathematical Society, Special Edition (2011) 11-26.
[3]	S. Beena, On £ and £' labelled graphs, Discrete Math. 309 (2009), 1783-1787.
[4]	S. Cichacz, Note on group distance magic graphs G[C4], Graphs Combin. 30 (2014), 565-571.
[5]	D. Froncek, Group distance magic labeling of Cartesian product of cycles, Australasian J. Combin. 55 (2013), 167-174.
[6]	D. Froncek, P. Kovar and T. Kovirova, Fair incomplete tournaments, Bull. of ICA 48 (2006) 31-33.
[7]	J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., DS6, http://www. combinatorics.org/issue/view/Surveys.
[8]	R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
[9]	M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australasian J. Combin. 28 (2003), 305-315.
[10]	S. B. Rao, T. Singh and V. Parameswaran, Some sigma labelled graphs I, in: S. Arumugam, B.D. Acharya and S.B. Rao (eds.), Graphs, Combinatorics, Algorithms and Applications, Narosa Publishing House, New Delhi (2004) 125-133.
[11]	P. M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962), 47-52.