Electronic Journal of Graph Theory and Applications 13 .
, 197Ae209 The distance magic property and two families of Cartesian product graphs Patrick Headley Mathematics Department Gannon University Erie.
Pennsylvania 16541
USA
headley001@gannon.
Abstract Let G = G(V.
E) be a simple graph.
The graph G is said toP be distance magic if there exists a bijection f : V Ie .
, 2, .
, |V |} and a constant s such that yOON .
= s for all x OO V.
this paper we show that the only distance magic graph of the form Kn 2Cm is K1 2C4 , and that m = 4 if Cm 2Kn,t is distance magic.
Necessary conditions are given for C4 2Kn,t to be distance magic when n > t.
These conditions are shown to be sufficient when n and t are both even.
We conclude with some examples of distance magic graphs of the form C4 2Kn,t with n > t, in particular constructing an infinite sequence of non-isomorphic distance magic graphs of this type.
Keywords: distance magic, graph labeling, cartesian product graph, complete graph, complete bipartite graph, cycle graph Mathematics Subject Classification : 05C76, 05C78 DOI: 10.
5614/ejgta.
Introduction Let G = G(V.
E) be a simple graph.
Given x OO V , let N .
be the set of vertices adjacent to The graph G is said to be distance magic if there exists a bijection f : V Ie .
, 2, .
, |V |} and Received: 8 May 2019.
Revised: 16 March 2025.
Accepted: 28 March 2025.
The distance magic property and two families of Cartesian product graphs Patrick Headley a constant s such that, for all x OO V , f .
= s.
yOON .
Such an f is a distance magic labeling of G.
This kind of labeling was first studied by Vilfred .
, who called it a -labeling.
The term 1-vertex magic labeling is also used.
Surveys include .
and Section 5.
6 of .
Let G and H be two graphs with vertex sets V (G) and V (H), respectively.
The Cartesian product G2H is a graph with vertex set V (G) y V (H).
In this graph, .
1 , h1 ) is adjacent to .
2 , h2 ) if and only if .
g1 = g2 and h1 is adjacent to h2 in H, or .
g1 is adjacent to g2 in G and h1 = h2 .
Let Kn be the complete graph on n vertices, let Cm be the cycle graph on m vertices .
Ou .
, and let Kn,t be the complete bipartite graph on n and t vertices.
In .
Seoud.
Abdel Maqsoud, and Aldiban asked which graphs of the types Kn 2Cm and Cm 2Kn,t are distance magic.
For some small values of the parameters, these graphs have been studied in isomorphic forms.
The graph K1 2Cm is isomorphic to Cm , known to be distance magic only for m = 4 .
The graph K3 2Cm is isomorphic to C3 2Cm , which is never distance magic .
The graph Cm 2K2,2 is isomorphic to Cm 2C4 , which also is never distance magic .
Seoud.
Abdel Maqsoud, and Aldiban showed that Kn 2C3 is not distance magic when n is odd, and that Kn 2Cm is not distance magic when n is even.
They also showed that Cm 2Kn,t is not distance magic in the following cases:
A Cm 2K1,n for n Ou 1 A Cm 2Kn,n for m odd and n = 2 A Cm 2Kn,n 1 for m O 1 .
and n even.
A positive result is given in .
, where Cichacz.
Froncek.
Krop, and Raridan showed that C4 2Kn,n is distance magic if and only if n is even and n > 2.
They also showed that Kn 2C4 is not distance magic for n Ou 2.
In this paper we show that Kn 2Cm is only distance magic when n = 1 and m = 4, and that it is necessary to have m = 4 for Cm 2Kn,t to be distance magic.
We establish conditions on n and t for distance magic labelings of C4 2Kn,t in the case that n > t.
When n and t are even these conditions are shown to be sufficient.
The smallest examples of such distance magic graphs are identified, and we show that there are in fact infinitely many such graphs up to graph isomorphism.
Kn 2Cm Let V be the set of vertices of G = Kn 2Cm .
The elements of V can be given as vi,j for 1 O i O n and j OO Z/mZ.
The vertex vi,j is adjacent to all vl,j with l = i and also to vi,jOe1 and vi,j 1 .
The main idea in this section is to look at the sum of the labels of the neighbors of all the vertices within each copy of Kn .
These sums satisfy a recurrence.
Methods for solving such recurrences are described in many standard discrete mathematics texts .
ee Section 7.
3 of .
, for The following lemma will be useful in this section and also in Section 3.
The distance magic property and two families of Cartesian product graphs Patrick Headley Lemma 2.
Let .
n } be a sequence of integers satisfying the recurrence rn arnOe1 rnOe2 = C, where C is a constant and a is an integer with .
> 2.
If .
n } is periodic, then .
n } is constant.
Proof.
A particular solution for the recurrence is rn = C/.
The characteristic equation x2 ax 1 = 0 has two real roots A1 and A2 with |A1 | > 1 and 0 < |A2 | < 1.
Thus, the general If k1 = 0, then .
n | grows without bound solution for the recurrence is rn = k1 An1 k2 An2 a 2 and is not periodic.
If k1 = 0, then rn has limit a 2 .
A periodic sequence can only have a limit if each term equals the limit, so .
n } is constant.
Let f be a real-valued function on V , with ai,j = f .
i,j ).
Let sj = ni=1 ai,j for all j.
Lemma 2.
If yOON .
= s for all vertices x of Kn 2Cm , then sjOe1 .
Oe .
sj sj 1 = ns for all j OO Z/mZ.
P P
Proof.
Consider the sum ni=1 yOON .
i,j ) f .
On the one hand, by assumption, the inner sum is always s, so the double sum is ns.
On the other hand, each vertex vi,j is adjacent to the other .
Oe .
vertices vl,j with l = i, and each vertex vi,jOe1 or vi,j 1 is adjacent to vl,j if and only if l = i.
Thus, every term of sj is included in the double sum .
Oe .
times, every term of sjOe1 and sj 1 is included once, and there are no remaining terms.
Corollary 2.
If yOON .
= s for all vertices x of Kn 2Cm , and n Ou 4, then all of the sj are Proof.
Let rj = sj .
for all natural numbers j.
By Lemmas 2.
1 and 2.
2, the sequence .
j } is constant.
Thus, all of the sj are equal.
Lemma 2.
Assume f : V Ie .
, .
, n.
is a distance magic labeling of Kn 2Cm .
If f .
i,j ) = ai,j , then ai,j Oe ai,j 6 = aiA ,j Oe aiA ,j 6 for all 1 O i, iA O n and all j OO Z/mZ.
Proof.
Assume i = iA , since otherwise the statement is trivial.
The vertices vi,j and viA ,j have all of the vertices vl,j with l = i, iA as common neighbors.
Thus, in a distance magic labeling, the labels of the three remaining neighbors for each vertex must have the same sum:
aiA ,j ai,jOe1 ai,j 1 = ai,j aiA ,jOe1 aiA ,j 1 .
Thus, ai,j Oe aiA ,j = .
i,jOe1 Oe aiA ,jOe1 ) .
i,j 1 Oe aiA ,j 1 ).
Since this is true for all j, we also have ai,j 1 Oe aiA ,j 1 = .
i,j Oe aiA ,j ) .
i,j 2 Oe aiA ,j 2 ), ai,j 2 Oe aiA ,j 2 = .
i,j 1 Oe aiA ,j 1 ) .
i,j 3 Oe aiA ,j 3 ).
Combining these equations leads to ai,j 3 Oe aiA ,j 3 = .
i,j 2 Oe aiA ,j 2 ) Oe .
i,j 1 Oe aiA ,j 1 ) = .
i,j 1 Oe aiA ,j 1 ) Oe .
i,j Oe aiA ,j ) Oe .
i,j 1 Oe aiA ,j 1 ) = Oe.
i,j Oe aiA ,j ).
Similarly, ai,j 6 OeaiA ,j 6 = Oe.
i,j 3 OeaiA ,j 3 ), so ai,j 6 OeaiA ,j 6 = ai,j OeaiA ,j , and thus ai,j Oeai,j 6 = aiA ,j Oe aiA ,j 6 .
The distance magic property and two families of Cartesian product graphs Patrick Headley Theorem 2.
The graph G = Kn 2Cm is distance magic if and only if n = 1 and m = 4.
Proof.
If G = K1 2C4 then G has the distance magic labeling a1,1 = 1, a1,2 = 2, a1,3 = 4, a1,4 = 3.
Otherwise, assume as in the previous theorem that the ai,j give a distance magic labeling of G.
Since the cases n = 1, n = 2, and n = 3 are known to satisfy the theorem .
ee the Introductio.
, we can assume n Ou 4.
Applying Lemma 2.
3, for a fixed j let d be the common value of ai,j Oe ai,j 6 for all i.
Thus, ai,j = .
i,j 6 .
= sj 6 nd.
By Corollary 2.
1, sj = sj 6 , so d = 0.
Thus, ai,j = ai,j 6 for all i, which can only happen if vi,j and vi,j 6 are the same vertex.
This implies that m divides 6, so either m = 3 or m = 6.
But m = 3 by .
, so assume m = 6, and recall that n cannot be even, also by .
Each sj must be 1/6 of the sum of all of the labels, so n.
1 6n.
which is not an integer when n is odd.
Thus.
G cannot be distance magic when n Ou 4.
Cm 2Kn,t We will describe Cm 2Kn,t as having vertex set V consisting of the vertices vi,j for i OO Z/mZ and 1 O j O n, and the vertices wi,k for i OO Z/mZ and 1 O k O t.
For all i, j, k the vertex vi,j is adjacent to viOe1,j and vi 1,j , the vertex wi,k is adjacent to wiOe1,k and wi 1,k and the vertex vi,j is adjacent to wi,k .
Let P function on V .
Let ai,j = f .
i,j ) and bi,k = f .
i,k ).
For all i, let P f be a real-valued ci = nj=1 ai,j and di = tk=1 bi,k .
Lemma 3.
Suppose yOON .
= s for all vertices x in Cm 2Kn,t .
Then ciOe1 .
Oe n.
ci 1 ci 3 = n.
Oe .
s and diOe1 .
Oe n.
di 1 di 3 = t.
Oe .
s for all i.
Proof.
For a fixed i, the n vertices vi,j contain one neighbor of each viOe1,j and each vi 1,j for 1 O j O n.
Each vertex vi,j is a neighbor of all of the wi,k as well.
This accounts for all neighbors of the vi,j , so, for all i, f .
= ciOe1 ndi ci 1 = ns.
j=1 yOON .
i,j ) Similarly, for all i, f .
= diOe1 tci di 1 = ts.
k=1 yOON .
i,k ) To find a recurrence for the ci , note that eliminating di from the system ciOe1 ndi ci 1 = ns The distance magic property and two families of Cartesian product graphs Patrick Headley di tci 1 di 2 = ts leads to ndi 2 = n.
Oe .
s ciOe1 .
Oe n.
ci 1 .
Plugging this into ci 1 ndi 2 ci 3 = ns produces the desired equation.
The proof for the di recurrence is similar.
Lemma 3.
If yOON .
= s for all vertices x in Cm 2Kn,t , and nt > 4, then all of the ci are equal, and all of the di are equal.
Proof.
If nt > 4, then 2 Oe nt < Oe2, so we can apply Lemma 2.
1 as in the proof of Corollary 2.
to the recurrence ciOe1 .
Oe n.
ci 1 ci 3 = n.
Oe .
s to see that ciOe1 = ci 1 for all i.
Similarly, the recurrence for the di shows that diOe1 = di 1 for all But then the equations of Lemma 3.
1 can be rewritten for all i as .
Oe n.
ciOe1 = n.
Oe .
s, .
Oe n.
diOe1 = t.
Oe .
Thus, for all i, ts.
Oe .
Oe .
and di = nt Oe 4 nt Oe 4 If the assumptions in the lemma hold, we can take c to be the shared value of the ci , and d to be the shared value of the di .
Theorem 3.
If m = 4, then Cm 2Kn,t is not distance magic.
Proof.
All of the cases with nt O 4 have already been examined .
ee the Introductio.
Thus, assume nt > 4 so that Lemma 3.
2 applies.
In a distance magic labeling, the sum of the labels of the neighbors of vi,j would be aiOe1,j ai 1,j d.
The sum of the labels of the neighbors of vi 2,j would be ai 1,j ai 3,j d.
For these two sums to be equal, aiOe1,j must equal ai 3,j , so viOe1,j and vi 3,j are the same vertex.
This is only possible if m divides 4.
Since m Ou 3, we conclude that m = 4.
The Case C4 2Kn,t Given that the case n = t has been studied in .
, and the case t = 1 in .
, in this section we will assume that n > t Ou 2.
To consider what a distance magic labeling of C4 2Kn,t must look like, first note the following:
Lemma 4.
In a distance magic labeling of C4 2Kn,t , the sums aiOe1,j ai 1,j are equal for all i, j, and the sums biOe1,k bi 1,k are equal for all i, k.
The distance magic property and two families of Cartesian product graphs Patrick Headley Proof.
The sum of the labels of the neighbors of vi,j is aiOe1,j ai 1,j d, and this must be the same sum for all i, j if the labeling is distance magic.
Similarly, biOe1,k bi 1,k c is the same for all i, k.
We can give expressions for these sums:
Lemma 4.
In a distance magic labeling of C4 2Kn,t , aiOe1,j ai 1,j = .
Oe .
n 4t .
2nt Oe 2n Oe 2t biOe1,k bi 1,k = .
Oe .
n 4t .
2nt Oe 2n Oe 2t for all i, j, and for all i, k.
Proof.
The sum 4c 4d must be the sum of the labels of all the vertices, and thus the sum of all the integers from 1 to 4n 4t, so using the formulas found in the proof of Lemma 3.
2 we get 4nts Oe 8ns 4nts Oe 8ts .
n 4t .
nt Oe 4 nt Oe 4 Solving this for s gives .
n 4t .
t Oe .
4nt Oe 4n Oe 4t We can plug this back in to get an expression for 4c in terms of just n and t:
4nt Oe 8n .
t Oe 2.
n 4t .
nt Oe 4 nt Oe n Oe t But 4c is the sum of all of the ai,j , and thus the sum of the 2n equal sums aiOe1,j ai 1,j , so aiOe1,j ai 1,j = .
Oe .
n 4t .
2nt Oe 2n Oe 2t for all i, j.
The proof of the other equation is similar.
Corollary 4.
In a distance magic labeling of C4 2Kn,t , .
Oe .
n 4t .
Oe .
n 4t .
2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t are both positive integers, and .
t Oe 2.
n 4t .
t Oe 2.
n 4t .
nt Oe n Oe t nt Oe n Oe t are both positive integer multiples of 4.
The distance magic property and two families of Cartesian product graphs Patrick Headley Proof.
The first part is obvious.
Multiplying the first two expressions by 2n and 2t respectively produces the final two expressions, which are the values of 4c and 4d.
Lemma 4.
2 also implies that, if n > t and C4 2Kn,t is distance magic, the integers from 1 to 4n 4t can be partitioned into sets of size two such that the pairsums .
hat is, the sum of the elements in each se.
take only the two values shown in the lemma, with both values actually occurring .
nder the assumption n > t, they will not be equa.
It turns out that such a partition, if it exists, is unique.
The following definition characterizes these partitions.
Definition 4.
Let I = {P.
P 1, .
Q Oe 1.
Q} be a non-empty interval of integers .
f length is an integer, and u and Q Oe P .
Suppose and are positive integers such that u = QOeP u are both even.
An , - partition of the interval is constructed as follows.
First, partition I into sets A and B by letting the smallest integers of I belong to A, the next smallest integers belong to B, the next smallest integers belong to A, and so on, until the largest integers are assigned to B.
The , -partition is the refinement of this partition into sets of size two by pairing the i-th smallest integer of A with the i-th largest integer of A for all 1 O i O 12 u, and by pairing the i-th smallest integer of B with the i-th largest integer of B for all 1 O i O 21 u.
Note that the conditions on and guarantee that no integer in I is Aoleft overAo at either step in the construction.
Also note that the subsets of A in the , - partition all have the same pairsum, as do the subsets of B.
This kind of partition was constructed by Anholcer and Cichacz in the proof of Theorem 2.
2 of .
, and the proof of the next lemma is essentially identical to what is found there.
Lemma 4.
3 (Anholcer.
Cichacz .
Suppose the interval I = {P.
P 1, .
Q Oe 1.
Q} of integers can be partitioned into sets of size 2, with the pairsums being L or N , and both pairsums occurring at least once.
Then the partition must be an , -partition.
Assuming L < N , we have = N Oe P Oe Q and = P Q Oe L.
Proof.
Since the mean pairsum has to be P Q, we must have L < P Q < N .
Each integer from P to N Oe Q Oe 1 is too small to be part of a pair with sum N , so the partition must include {P.
L Oe P }, {P 1.
L Oe P Oe .
, .
, {N Oe Q Oe 2.
L Oe N Q .
, {N Oe Q Oe 1.
L Oe N Q .
, all with pairsum L.
Similarly, the integers from L Oe P 1 to Q are too large to be part of a pair with sum L, so the partition must also include {N Oe L P Oe 1.
L Oe P .
, {N Oe L P Oe 2.
L Oe P .
, .
, {N Oe Q 1.
Q Oe .
, {N Oe Q.
Q}, all with pairsum N .
Thus, the smallest N Oe P Oe Q integers in I .
rom P to N Oe Q Oe .
belong to pairs of sum L, and the next-smallest P Q Oe L integers .
rom N Oe Q to N Oe L P Oe .
belong to pairs of sum N .
Similarly, the largest P Q Oe L integers .
rom L Oe P 1 to Q) belong to pairs of sum N , and the next-largest N Oe P Oe Q integers .
rom L Oe N Q 1 to L Oe P ) belong to pairs of sum L.
Thus, the only possible values for and are = N Oe P Oe Q and = P Q Oe L.
If there is any overlap at all between the interval from P to N Oe L P Oe 1 and the interval from L Oe N Q 1 to Q, then the intervals must be identical to avoid a contradiction.
Thus, we have an , - partition of the interval .
ith u = .
If the intervals are disjoint, and the pairs already listed partition I by themselves, we have an , - partition with u = 2.
Otherwise, the intervals are disjoint and there is a non-empty interval from N Oe L P to L Oe N Q.
This interval itself meets The distance magic property and two families of Cartesian product graphs Patrick Headley the conditions of the lemma, and by induction the partition of this interval is an , - partition, with = N Oe(N OeL P )Oe(LOeN Q) = N OeP OeQ and = (N OeL P ) (LOeN Q)OeL = P Q Oe L.
Combining this partition with the pairs already listed gives an , - partition of the original interval.
In a distance magic labeling of C4 2Kn,t , we would have P = 1 and Q = 4n 4t.
Since by assumption n > t, the expression for aiOe1,j ai 1,j in Lemma 4.
2 must be L, and the expression for biOe1,k bi 1,k must be N .
Thus, =N OeP OeQ= .
Oe .
n 4t .
n 4t .
Oe .
n Oe .
n 4t .
= 2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t = P Q Oe L = .
n 4t .
Oe .
Oe .
n 4t .
n 4t .
Oe .
t 2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t Since .
n 4t .
Oe .
2nt Oe 2n Oe 2t must be a divisor of the length 4n 4t of the interval I, we get another integrality condition:
Corollary 4.
In a distance magic labeling of C4 2Kn,t with n > t, 8nt Oe 8n Oe 8t .
n 4t .
Oe .
is a positive integer.
We can now give a partial converse to Corollaries 4.
1 and 4.
Theorem 4.
Assume n and t are positive integers with n and t both even and n > t.
Oe .
n 4t .
Oe .
n 4t .
2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t are both positive integers, and 8nt Oe 8n Oe 8t .
n 4t .
Oe .
is a positive integer, then C4 2Kn,t is distance magic.
Proof.
Let .
Oe .
n 4t .
Oe .
n 4t .
and N = 2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t and also let = N Oe.
n 4t .
= .
n 4t .
Oe .
n 4t .
Oe .
t and = 4n 4t 1OeL = 2nt Oe 2n Oe 2t 2nt Oe 2n Oe 2t The distance magic property and two families of Cartesian product graphs Patrick Headley We wish to show that there is an , - partition of the interval from 1 to 4n 4t with pairsums L and N .
By assumption.
L and N are positive integers, and thus and are as well .
ote that L > 0 implies t Ou 4, and thus 2nt Oe 2n Oe 2t is positiv.
Also, .
/( ) = 8nt Oe 8n Oe 8t .
n 4t .
Oe .
is a positive integer that we can call u.
Note that u = .
n 4t .
Oe .
t Oe n Oe .
= 4n, .
n 4t .
Oe .
2nt Oe 2n Oe 2t and similarly u = 4t.
Since u and u are even, an , - partition of the interval from 1 to 4n 4t exists, with A consisting of 4n integers in u intervals of length and B consisting of 4t integers in u intervals of length .
The pairsums can be found by adding the smallest and largest integers of A and B respectively, so these are 1 .
n 4t Oe ) = L, and ( .
= N .
Note that .
t Oe 2.
n 4t .
2nL = nt Oe n Oe t is a multiple of 4 since n is even, so let c be such that 2nL = 4c, and similarly let d be such that 2tN = 4d.
Suppose now that we can label the vertices of C4 2Kn,t with the integers from 1 to 4n 4t so that .
the , - partition consists of the sets .
iOe1,j , ai 1,j } for all i, j and .
iOe1,k P, bi 1,k } for all i, k, .
the values of ci = nj=1 ai,j are all equal, and .
the values of di = tk=1 bi,k are all Then ci = c for all i since the ci have sum 4c, and similarly di = d for all i.
The labeling will then be distance magic, since, for all i, j, the sum of the labels of the neighbors of vi,j is L d=L .
Oe .
n 4t .
Oe .
n 4t .
2nt Oe 2n Oe 2t 4nt Oe 4n Oe 4t .
n 4t .
t Oe .
4nt Oe 4n Oe 4t and, for all i, k, the sum of the labels of the neighbors of wi,k is N c=N .
Oe .
n 4t .
Oe .
n 4t .
2nt Oe 2n Oe 2t 4nt Oe 4n Oe 4t .
n 4t .
t Oe .
4nt Oe 4n Oe 4t To this end, a u y matrix MA = .
p,q ) will be constructed that will contain the i values for all integers in A.
To be more precise, if mp,q = i then q .
Oe .
( ) will be ai,j for some j.
It is sufficient for MA to meet three conditions.
First, mp,q = mu 1Oep, 1Oeq 2.
that is, two entries symmetric over the center of the matrix must differ by 2 .
, since these are the matrix entries corresponding to paired labels.
Second, each i OO Z/4Z must appear exactly u/4 Third, the sums mp,q =i .
Oe .
( )] must be equal for all i, since these sums are the The distance magic property and two families of Cartesian product graphs Patrick Headley P of the ci .
Note that it will be sufficient Pto replace this third condition with the conditions that .
mp,q =i q is the same for all i, and .
mp,q =i p is the same for all i.
A matrix will be called u, -balanced if it meets all of these conditions.
It is easy to see that, if a matrix is u, -balanced, so is its transpose.
Also, if a matrix is constructed from u, -balanced blocks, and each block is identical to a block in the position symmetric over the center of the matrix, then the entire matrix is u, -balanced.
The following matrices are u, -balanced:
M1 =
0 1 2 3 3 2 1 0 2 3 0 1 1 0 3 2
0 1 2 3 2 3 0 1
M2 =
3 2 1 0 1 0 3 2
0 1 2 3
3 2 1 0
M3 =
2 3 0 1 .
1 0 3 2
Note that u is divisible by 8, since u = 4n and n is even.
If u is divisible by 16, the entire matrix MA can be filled by copies of a single one of M1 .
M2 .
M3 .
M2T or M1T .
Assume u is divisible by 8 but not 16.
As a first case, assume u is odd and is divisible by 8 but not 16.
If u = 1, then = 8, since u = 4n = 8 implies n = 2, contradicting n > t Ou 2.
Thus.
Ou 24.
The leftmost and rightmost entries of MA can be filled with copies of M1 until either the central 24 or 40 positions remain.
These positions can be filled with 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 3, 3, 1, 2, 0, 2, 0, 3, 1, 3, 1, 2, 0, 2, 0, 3, 1, 1, 0, 3, 2, 2, 3, 0, 1, 1, 0, 3, 2 or just the central 24 values in this list as necessary.
If u Ou 3, then the top and bottom rows of MA can be filled with copies of M2 until either the 3 or 5 central rows remain.
These can be filled with copies of the u, -balanced matrix
0 1 2 3 3 2 1 0
0 1 2 3 3 1 2 0
2 0 3 1 3 1 2 0
2 0 3 1 1 0 3 2
2 3 0 1 1 0 3 2
when 5 rows remain, or copies of this matrix with the top and bottom rows removed when 3 rows Next, assume u is divisible by 2 but not 4, and is divisible by 4 but not 8.
If u = 2, then, since u = 8, it must be that Ou 12.
The leftmost and rightmost columns of MA can be filled with copies of M2 until a central 2 y 12 or 2 y 20 block remains, and this can be filled with the u, - balanced matrix
0 1 2 3 2 0 2 0 0 1 2 3 3 1 3 1 3 2 1 0
2 3 0 1 3 1 3 1 1 0 3 2 2 0 2 0 1 0 3 2
The distance magic property and two families of Cartesian product graphs Patrick Headley or with its central 12 columns, as necessary.
If u Ou 6, the top and bottom rows can be filled with copies of M3 until only the central 6 or 10 rows remain.
These can be filled with copies of the u, -balanced matrix
0 1 2 3
3 2 1 0
0 1 2 3
3 1 2 0
2 0 3 1
3 1 2 0 ,
2 0 3 1
1 0 3 2
2 3 0 1
1 0 3 2
or copies of this matrix with the top two and bottom two rows removed.
The other cases with u divisible by 8 but not 16 are just transposed versions of the cases already considered.
With MA constructed we can proceed to construct a u y matrix MB consisting of the i values of the bi,k in essentially the same way .
his matrix can be called u, - balance.
Note that, once we determine which subset of the integers from 1 to 4n 4t will make up the values a0,j , the j indices can be assigned arbitrarily, and then, for a particular j, a2,j must be the integer paired with a0,j in the , - partition.
We can proceed in a similar fashion to assign the values of a1,j and a3,j for all j, the values of b0,k and b2,k for all k, and the values of b1,k and b3,k for all k, resulting in a distance magic labeling of the entire graph.
A Maple search for examples with n O 50000 shows that C4 2Kn,t is distance magic for the following values of n and t, shown with the corresponding values of u, , and :
2514 2130 6 1676 1420
8192 7232 8 4096 3616
10074 7866 4 10074 7866
20210 18290 10 8084 7316
42072 38712 12 14024 12904
If n is odd and t is even, then the required expressions from Corollary 4.
1 cannot both be multiples of 4, since the only even factors in their numerators would be t Oe 2 and t, which cannot both be multiples of 4.
Thus, if n is odd and C4 2Kn,t is distance magic, t must be odd as well.
A Maple search found no examples with n O 50000 and n odd that met all of the integrality conditions, so it is an open question whether such examples exist and lead to distance magic labelings.
Using a different approach it is possible to show that C4 2Kn,t is distance magic for infinitely many pairs .
, .
with n > t.
For a particular value of u, the values of and must satisfy a quadratic diophantine equation, and this equation possibly has an infinite family of solutions in positive integers.
The distance magic property and two families of Cartesian product graphs Patrick Headley Theorem 4.
Let 1 = 0 and 1 = 7.
Let the sequences .
} and .
} be defined recursively by i 1 = 5i 2i Oe 6 and i 1 = 2i i 1.
Then i 1 > i and i 1 > i for all i, and C4 2Kn,t is distance magic for all i Ou 1 when n = 14 8i 2 and t = 14 8i 2 .
Proof.
If i Ou 0 and i Ou 7, then i 1 = 5i 2i Oe 6 > 5i 8 > i , and i 1 = 2i i 1 > i , so both sequences are increasing by induction.
In a distance magic labeling of C4 2Kn,t with u = 1, each vi,j would be adjacent to a pair of v-vertices with sum 1, and to a set of w-vertices with label sum equal to 1/4 of the sum of the integers from 1 to .
Meanwhile, each wi,k must be adjacent to a pair of w-vertices with sum 2 1, and to a set of v-vertices with label sum equal to 1/4 of the sum of the integers from 1 to .
Thus, the equation 1 ( .
= 2 1
must be satisfied, and it is equivalent to 2 Oe 2 Oe 2 9 7 = 0.
Methods for solving two-variable quadratic diophantine equations are due to Euler and Lagrange .
The site .
was used to find the sequences stated in the theorem.
It is straightforward to show by induction that the terms of the sequence of pairs .
, i ) satisfy the quadratic equation and that i > i > 0 for i Ou 3.
It can also be checked that this sequence is cyclic with a period of 8 when taken modulo 8, and i O i O 0 .
when i O 2 .
Now suppose n = 14 8i 2 and t = 41 8i 2 for some i Ou 1.
Then n and t are both even and n > t Ou 2.
Using a u, - balanced matrix of dimension 1 y 4n and a u, -balanced matrix of dimension 1 y 4t, a labeling can be constructed that is guaranteed by the quadratic equation to be distance magic.
More families of distance magic graphs can be found by taking other values of u and solving the corresponding quadratic diophantine equations.
References