On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs
Magic rectangles are a classical generalization of the well-known magic squares, and they are related to graphs. A graph G is called degree-magic if there exists a labelling of the edges by integers 1, 2, . . . , |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2019
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/188480 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs / P. Inpoonjai, T. Jiarasuksakun // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 107–122. — Бібліогр.: 15 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859753374312824832 |
|---|---|
| author | Inpoonjai, P. Jiarasuksakun, T. |
| author_facet | Inpoonjai, P. Jiarasuksakun, T. |
| citation_txt | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs / P. Inpoonjai, T. Jiarasuksakun // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 107–122. — Бібліогр.: 15 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | Magic rectangles are a classical generalization of the well-known magic squares, and they are related to graphs. A graph G is called degree-magic if there exists a labelling of the edges by integers 1, 2, . . . , |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1 + |E(G)|) deg(v)/2. Degree-magic graphs extend supermagic regular graphs. In this paper, we present a general proof of the necessary and sufficient conditions for the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs. We apply this existence to construct supermagic regular graphs and to identify the sufficient condition for even n-tuple magic rectangles to exist.
|
| first_indexed | 2025-12-02T00:31:08Z |
| format | Article |
| fulltext |
“adm-n3” — 2019/10/20 — 9:35 — page 107 — #109
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 28 (2019). Number 1, pp. 107–122
c© Journal “Algebra and Discrete Mathematics”
On the existence of degree-magic labellings of the
n-fold self-union of complete bipartite graphs
Phaisatcha Inpoonjai and Thiradet Jiarasuksakun
Communicated by D. Simson
Abstract. Magic rectangles are a classical generalization of
the well-known magic squares, and they are related to graphs. A
graph G is called degree-magic if there exists a labelling of the edges
by integers 1, 2, . . . , |E(G)| such that the sum of the labels of the
edges incident with any vertex v is equal to (1 + |E(G)|) deg(v)/2.
Degree-magic graphs extend supermagic regular graphs. In this
paper, we present a general proof of the necessary and sufficient
conditions for the existence of degree-magic labellings of the n-fold
self-union of complete bipartite graphs. We apply this existence to
construct supermagic regular graphs and to identify the sufficient
condition for even n-tuple magic rectangles to exist.
1. Introduction
We consider simple graphs without isolated vertices. If G is a graph,
then V (G) and E(G) stand for the vertex set and the edge set of G,
respectively. Cardinalities of these sets are called the order and size of G.
Let a graph G and a mapping f from E(G) into positive integers be
given. The index mapping of f is the mapping f∗ from V (G) into positive
The authors would like to thank the anonymous referee for careful reading and the
helpful comments improving this paper.
2010 MSC: Primary 05C78; Secondary 05B15.
Key words and phrases: regular graphs, bipartite graphs, tripartite graphs, su-
permagic graphs, degree-magic graphs, balanced degree-magic graphs, magic rectangles.
“adm-n3” — 2019/10/20 — 9:35 — page 108 — #110
108 On the existence of degree-magic labellings
integers defined by
f∗(v) =
∑
e∈E(G)
η(v, e)f(e) for every v ∈ V (G),
where η(v, e) is equal to 1 when e is an edge incident with vertex v, and
0 otherwise. An injective mapping f from E(G) into positive integers
is called a magic labelling of G for an index λ if its index mapping f∗
satisfies
f∗(v) = λ for all v ∈ V (G).
A magic labelling f of a graph G is called a supermagic labelling if the set
{f(e) : e ∈ E(G)} consists of consecutive positive integers. We say that a
graph G is supermagic (magic) whenever a supermagic (magic) labelling
of G exists.
A bijective mapping f from E(G) into {1, 2, . . . , |E(G)|} is called a
degree-magic labelling (or d-magic labelling) of a graph G if its index
mapping f∗ satisfies
f∗(v) =
1 + |E(G)|
2
deg(v) for all v ∈ V (G).
A d -magic labelling f of a graph G is called balanced if for all v ∈ V (G),
the following equation is satisfied
|{e ∈ E(G) : η(v, e) = 1, f(e) 6 ⌊|E(G)|/2⌋}|
= |{e ∈ E(G) : η(v, e) = 1, f(e) > ⌊|E(G)|/2⌋}|.
We say that a graph G is degree-magic (balanced degree-magic) or only
d-magic when a d -magic (balanced d -magic) labelling of G exists.
The concept of magic graphs was introduced by Sedláček [1]. Later,
supermagic graphs were introduced by Stewart [2]. There are now many
papers published on magic and supermagic graphs; see Gallian [3] for more
comprehensive references. The concept of degree-magic graphs was then in-
troduced by Bezegová and Ivančo [4] as an extension of supermagic regular
graphs. They established the basic properties of degree-magic graphs and
characterized degree-magic and balanced degree-magic complete bipartite
graphs in [4]. They also characterized degree-magic complete tripartite
graphs in [5]. Some of these concepts are investigated in [6-8].
Magic rectangles are a natural generalization of the magic squares
which have widely intrigued mathematicians and the general public. A
magic (p, q)-rectangle R is a p × q array in which the first pq positive
“adm-n3” — 2019/10/20 — 9:35 — page 109 — #111
P. Inpoonjai, T. Jiarasuksakun 109
integers are placed such that the sum over each row of R is constant and
the sum over each column of R is another (different if p 6= q) constant.
Harmuth [9, 10] studied magic rectangles over a century ago and proved
that
Theorem 1. ([9, 10]) For p, q > 1, there is a magic (p, q)-rectangle R if
and only if p ≡ q (mod 2) and (p, q) 6= (2, 2).
In 1990, Sun [11] studied the existence of magic rectangles. Later,
Bier and Rogers [12] studied on balanced magic rectangles, and Bier and
Kleinschmidt [13] studied about centrally symmetric and magic rectangles.
Then Hagedorn [14] presented a simplified modern proof of the necessary
and sufficient conditions for a magic rectangle to exist. The concept of
magic rectangles was generalized to n-dimensions and several existence
theorems were proven by Hagedorn [15].
We will hereinafter use the following auxiliary results from these
studies.
Theorem 2. ([4]) Let G be a regular graph. Then G is supermagic if and
only if it is d-magic.
Theorem 3. ([4]) Let G be a d-magic graph of even size. Then every
vertex of G has an even degree and every component of G has an even
size.
Theorem 4. ([4]) Let G be a balanced d-magic graph. Then G has an
even number of edges and every vertex has an even degree.
Theorem 5. ([4]) Let G be a d-magic graph having a half-factor. Then
2G is a balanced d-magic graph.
Theorem 6. ([4]) Let H1 and H2 be edge-disjoint subgraphs of a graph
G which form its decomposition. If H1 is d-magic and H2 is balanced
d-magic, then G is a d-magic graph. Moreover, if H1 and H2 are both
balanced d-magic, then G is a balanced d-magic graph.
Proposition 1. ([4]) For p, q > 1, the complete bipartite graph Kp,q is
d-magic if and only if p ≡ q (mod 2) and (p, q) 6= (2, 2).
Theorem 7. ([4]) The complete bipartite graph Kp,q is balanced d-magic
if and only if the following statements hold:
(i) p ≡ q ≡ 0 (mod 2);
(ii) if p ≡ q ≡ 2 (mod 4), then min{p, q} > 6.
“adm-n3” — 2019/10/20 — 9:35 — page 110 — #112
110 On the existence of degree-magic labellings
2. The n-fold self-union of complete bipartite graphs
For any integer n > 1, the n-fold self-union of a graph G, denoted by
nG, is the union of n disjoint copies of G. For integers p, q > 1, we consider
the n-fold self-union nKp,q of complete bipartite graphs. Let nKp,q be a
d -magic graph. Since deg(v) is p or q and f∗(v) = (npq + 1) deg(v)/2 for
any v ∈ V (nKp,q), we then have
Proposition 2. Let nKp,q be a d-magic graph. Then the following condi-
tions hold:
(i) if n is odd, then p ≡ q (mod 2);
(ii) if n is even, then p ≡ q ≡ 0 (mod 2).
Theorem 8. Let nKp,q be a balanced d-magic graph. Then the following
conditions hold:
(i) p and q are both even;
(ii) if n is odd and p ≡ q ≡ 2 (mod 4), then min{p, q} > 6.
Proof. For any integer n > 1, suppose that nKp,q is balanced d -magic. By
Theorem 4, p and q are both even because nKp,q has vertices of degrees p
and q.
For any t ∈ {1, 2, . . . , n}, let Kt
2,2s be the tth copy of a graph K2,2s and
let et(vt) be its edge (vertex) corresponding to e ∈ E(K2,2s)(v ∈ V (K2,2s)).
Let f be a balanced d -magic labelling of a graph nK2,2s and let {ut, vt}
be a partite set of Kt
2,2s with two vertices. Put
At := {et ∈ E(Kt
2,2s) : η(u
t, et) = 1, f(et) 6 2ns}
and
Bt := {et ∈ E(Kt
2,2s) : η(w
t, et) = 1, f(et) 6 2ns}.
Clearly, At ∩Bt = ∅ and |At| = |Bt| = s because f is balanced d -magic.
We can see that any edge of Kt
2,2s is incident to either ut or wt and the
set of labels of edges incident to a vertex of degree two is {r, 4ns− r + 1}
for some r ∈ {1, 2, . . . , 2ns}. As a result, we have
4ns+ 1
2
2s =
|E(nK2,2s)|+ 1
2
deg(ut) = f∗(ut)
=
∑
et∈At
f(et) +
∑
et∈Bt
(4ns− f(et) + 1)
= (4ns+ 1)s+
∑
et∈At
f(et)−
∑
et∈Bt
f(et).
“adm-n3” — 2019/10/20 — 9:35 — page 111 — #113
P. Inpoonjai, T. Jiarasuksakun 111
This means that
∑
et∈At f(et) =
∑
et∈Bt f(et). Consequently,
(2ns+ 1)ns =
2ns
∑
i=1
i =
n
∑
t=1
(
∑
et∈At
f(et) +
∑
et∈Bt
f(et))
=
n
∑
t=1
(2
∑
et∈At
f(et)) = 2
n
∑
t=1
(
∑
et∈At
f(et)) ≡ 0 (mod 2).
Since n is odd, s is even. This proves that condition (ii) holds.
Proposition 2 allows the set of d -magic graphs nKp,q to be divided into
sets of odd and even d -magic graphs. Inspection quickly shows that for
(p, q) = (2, 2), a d -magic graph nK2,2 does not exist. In the next results,
we prove the existence of d -magic graphs nKp,q for other even integers
(p, q) 6= (2, 2).
Now let us consider a concept of a half-factor of a graph G defined by
Bezegová and Ivančo [4]. A spanning subgraph H of a graph G is called a
half-factor of G whenever degH(v) = degG(v)/2 for every vertex v ∈ V (G).
Note that a spanning subgraph of G with the edge set E(G)\E(H) is also a
half-factor of G. Similarly, if f is a balanced d -magic labelling of G, then the
spanning subgraphs with the edge sets {e ∈ E(G) : f(e) 6 ⌊|E(G)|/2⌋}
and {e ∈ E(G) : f(e) > ⌊|E(G)|/2⌋} are half factors of G.
Theorem 9. For even integers p, q > 1. If the complete bipartite graph
Kp,q is d-magic, then the following conditions hold:
(i) nKp,q is a d-magic graph for all odd integers n > 3;
(ii) nKp,q is a balanced d-magic graph for all even integers n > 2.
Proof. For any integer n > 2 and t ∈ {1, 2, . . . , n}, let Kt
p,q be the tth
copy of a graph Kp,q and let et(vt) be its edge (vertex) corresponding
to e ∈ E(Kp,q)(v ∈ V (Kp,q)). Since Kp,q is d -magic, there is a d -magic
labelling g of Kp,q. Since p and q are both even, there is a half-factor H of
Kp,q. First suppose that nKp,q = K1
p,q ∪K2
p,q ∪ · · · ∪Kn
p,q and we consider
a mapping f from E(nKp,q) into positive integers given by
f(et) =
{
g(e) + (t− 1)pq if e ∈ E(H),
g(e) + (n− t)pq if e ∈ E(Kp,q) \ E(H).
“adm-n3” — 2019/10/20 — 9:35 — page 112 — #114
112 On the existence of degree-magic labellings
We can then check that f is a bijection from E(nKp,q) onto {1, 2, . . . , npq}.
For any vertex vt ∈ V (Kt
p,q), we have
f∗(vt) =
∑
et∈E(Kt
p,q)
η(vt, et)f(et) =
∑
e∈E(H)
η(v, e)(g(e) + (t− 1)pq)
+
∑
e∈E(Kp,q)\E(H)
η(v, e)(g(e) + (n− t)pq)
=
∑
e∈E(H)
η(v, e)g(e) +
∑
e∈E(Kp,q)\E(H)
η(v, e)g(e) + (t− 1)pq degH(v)
+ (n− t)pq degKp,q−E(H)(v)
=
∑
e∈E(H)
η(v, e)g(e) +
∑
e∈E(Kp,q)\E(H)
η(v, e)g(e) +
(t− 1)pq
2
degKp,q
(v)
+
(n− t)pq
2
degKp,q
(v)
= g∗(v) +
(n− 1)pq
2
degKp,q
(v) =
pq + 1
2
degKp,q
(v)
+
(n− 1)pq
2
degKp,q
(v)
=
npq + 1
2
degKp,q
(v) =
npq + 1
2
degnKp,q
(vt).
Hence f is d -magic and nKp,q is a d -magic graph for all integers n > 2.
If n is even, then for any vt ∈ V (Kt
p,q) and t 6 n/2, we have
|{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) 6 npq/2}|
= degH(v) =
degKp,q
(v)
2
= degKp,q−E(H)(v)
= |{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) > npq/2}|,
and for any vt ∈ V (Kt
p,q) and t > n/2, we have
|{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) 6 npq/2}|
= degKp,q−E(H)(v) =
degKp,q
(v)
2
= degH(v)
= |{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) > npq/2}|.
Thus f is balanced d -magic and nKp,q is a balanced d -magic graph for
all even integers n > 2.
“adm-n3” — 2019/10/20 — 9:35 — page 113 — #115
P. Inpoonjai, T. Jiarasuksakun 113
Combining Proposition 1 and Theorem 9, we obtain the following
result.
Proposition 3. Let p and q be even positive integers with (p, q) 6= (2, 2).
Then the following conditions hold:
(i) nKp,q is a d-magic graph for all odd integers n > 1;
(ii) nKp,q is a balanced d-magic graph for all even integers n > 2.
Corollary 1. Let p and q be even positive integers with (p, q) 6= (2, 2). If
p = q, then nKp,q is a supermagic graph.
Proof. Follows from Theorem 2 and Proposition 3.
Example 1. Consider the complete bipartite graph K2,6. One can confirm
that K2,6 is d -magic, but it is not a balanced d -magic graph (see Figure 1),
and the labels on edges uivj of K2,6, where 1 6 i 6 2 and 1 6 j 6 6, are
shown in Table 1.
Then we can construct a balanced d -magic graph 4K2,6 (see Figure 2)
with the labels on edges utiv
t
j of 4K2,6, where 1 6 i 6 2, 1 6 j 6 6 and
1 6 t 6 4, in Table 2.
Theorem 10. Let p and q be integers with p, q > 1. If the complete
bipartite graph Kp,q is balanced d-magic, then nKp,q is a balanced d-magic
graph for all integers n > 2.
Proof. For any integer n > 2 and t ∈ {1, 2, . . . , n}, let Kt
p,q be the tth copy
of a graph Kp,q and let et(vt) be its edge (vertex) corresponding to e ∈
E(Kp,q)(v ∈ V (Kp,q)). Since Kp,q is balanced d -magic, there is a balanced
d -magic labelling g of Kp,q. Let H
′
1 := {e ∈ E(Kp,q) : g(e) 6 ⌊pq/2⌋} and
H
′
2 := {e ∈ E(Kp,q) : g(e) > ⌊pq/2⌋}. Thus, the spanning subgraphs H1
and H2 of Kp,q with the edge sets H
′
1 and H
′
2 are half-factors of Kp,q,
respectively. Suppose that nKp,q = K1
p,q∪K2
p,q∪· · ·∪Kn
p,q and we consider
a mapping f from E(nKp,q) into positive integers given by
f(et) =
{
g(e) + (t− 1)pq if e ∈ H
′
1,
g(e) + (n− t)pq if e ∈ H
′
2.
“adm-n3” — 2019/10/20 — 9:35 — page 114 — #116
114 On the existence of degree-magic labellings
Figure 1. A d -magic complete bipartite graph K2,6 with 8 vertices and 12
edges.
Vertices v1 v2 v3 v4 v5 v6
u1 1 11 3 9 8 7
u2 12 2 10 4 5 6
Table 1. The labels on edges of d -magic complete bipartite graph K2,6.
Figure 2. A balanced d -magic graph 4K2,6 with 32 vertices and 48 edges.
Vertices v11 v12 v13 v14 v15 v16
u11 37 47 39 9 8 7
u12 12 2 10 40 41 42
Vertices v21 v22 v23 v24 v25 v26
u21 25 35 27 21 20 19
u22 24 14 22 28 29 30
Vertices v31 v32 v33 v34 v35 v36
u31 13 23 15 33 32 31
u32 36 26 34 16 17 18
Vertices v41 v42 v43 v44 v45 v46
u41 1 11 3 45 44 43
u42 48 38 46 4 5 6
Table 2. The labels on edges of balanced d -magic graph 4K2,6.
“adm-n3” — 2019/10/20 — 9:35 — page 115 — #117
P. Inpoonjai, T. Jiarasuksakun 115
We can then check that f is a bijection from E(nKp,q) onto {1, 2, . . . npq}.
For any vertex vt ∈ V (Kt
p,q), we have
f∗(vt) =
∑
et∈E(Kt
p,q)
η(vt, et)f(et)
=
∑
e∈H
′
1
η(v, e)(g(e) + (t− 1)pq) +
∑
e∈H
′
2
η(v, e)(g(e) + (n− t)pq)
=
∑
e∈H
′
1
η(v, e)g(e) +
∑
e∈H
′
2
η(v, e)g(e) + (t− 1)pq degH1
(v)
+ (n− t)pq degH2
(v)
=
∑
e∈H
′
1
η(v, e)g(e) +
∑
e∈H
′
2
η(v, e)g(e) +
(t− 1)pq
2
degKp,q
(v)
+
(n− t)pq
2
degKp,q
(v)
= g∗(v) +
(n− 1)pq
2
degKp,q
(v) =
pq + 1
2
degKp,q
(v)
+
(n− 1)pq
2
degKp,q
(v)
=
npq + 1
2
degKp,q
(v) =
npq + 1
2
degnKp,q
(vt).
Hence f is a d -magic labelling. For vt ∈ V (Kt
p,q) and t 6 (n+ 1)/2, we
have
|{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) 6 ⌊npq/2⌋}|
= degH1
(v) =
degKp,q
(v)
2
= degH2
(v)
= |{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) > ⌊npq/2⌋}|,
and for any vt ∈ V (Kt
p,q) and t > (n+ 1)/2, we have
|{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) 6 ⌊npq/2⌋}|
= degH2
(v) =
degKp,q
(v)
2
= degH1
(v)
= |{et ∈ E(Kt
p,q) : η(v
t, et) = 1, f(et) > ⌊npq/2⌋}|.
Hence f is balanced d -magic. Therefore, nKp,q is a balanced d -magic
graph for all integers n > 2.
“adm-n3” — 2019/10/20 — 9:35 — page 116 — #118
116 On the existence of degree-magic labellings
According to Theorems 7 and 10, we obtain the following result.
Proposition 4. Let p and q be even positive integers and the following
condition holds:
if p ≡ q ≡ 2 (mod 4), then min{p, q} > 6.
Then nKp,q is a balanced d-magic graph for all integers n > 1.
3. A construction of supermagic regular graphs
In this section we construct supermagic regular graphs by applying
the existence of the n-fold self-union of complete bipartite graphs. Herein,
we consider the ξ-multiplication of a graph introduced by Bezegová and
Ivančo [4] to prove the next result. Let G be a graph and ξ be a mapping
from V (G) into the positive integers. The ξ-multiplication of G, denoted
by Gξ, is a graph whose vertices are all ordered pairs (v, i), where v ∈ V (G)
and 1 6 i 6 ξ(v), and two vertices (u, i), (v, j) are joined by an edge in
Gξ if and only if u, v are adjacent in G. Note that Gξ is isomorphic to
lexicographic product G[Dn] of G and a totally disconnected graph Dn,
when ξ(v) = n for all v ∈ V (G).
Proposition 5. For any integer n > 1 and t ∈ {1, 2, . . . , n}. Let Gt be the
tth copy of a graph G and let vt be its vertex corresponding to v ∈ V (G).
Let ξ be a mapping from V (nG) into even positive integers such that the
following conditions hold:
(i) ξ(vt) = ξ(vs) for all t, s ∈ {1, 2, . . . , n};
(ii) for any adjacent vertices ut, vt ∈ V (Gt), if ξ(ut) ≡ ξ(vt) ≡ 2
(mod 4), then min{ξ(ut), ξ(vt)} > 6.
Then the ξ-multiplication (nG)ξ is a balanced d-magic graph.
Proof. For any integer n > 1 and t ∈ {1, 2, . . . , n}. Let edge et = utvt ∈
E(Gt) and let (Gt
et
)ξ be a subgraph of (Gt)ξ induced by {(ut, i) : 1 6
i 6 ξ(ut)} ∪ {(vt, j) : 1 6 j 6 ξ(vt)}. Evidently, (Gt
et
)ξ is isomorphic to a
complete bipartite graph Kξ(ut),ξ(vt). According to Theorem 7, Kξ(ut),ξ(vt)
is a balanced d -magic graph. By condition (i), we obtain that Kξ(ut),ξ(vt)
is isomorphic to Kξ(us),ξ(vs) for all t, s ∈ {1, 2, .., n}. Thus, by Proposi-
tion 4,
⋃n
t=1Kξ(ut),ξ(vt) is a balanced d -magic graph. Since
⋃n
t=1(G
t
et
)ξ is
isomorphic to
⋃n
t=1Kξ(ut),ξ(vt),
⋃n
t=1(G
t
et
)ξ is a balanced d -magic graph.
The ξ-multiplication (nG)ξ is decomposed into edge-disjoint subgraphs
⋃n
t=1(G
t
et
)ξ for all et ∈ E(Gt). Therefore, by Theorem 6, (nG)ξ is a bal-
anced d -magic graph.
“adm-n3” — 2019/10/20 — 9:35 — page 117 — #119
P. Inpoonjai, T. Jiarasuksakun 117
Note that the subgraph of (nG)ξ induced by
⋃n
t=1{(v
t, 1) : vt ∈ V (Gt)}
is isomorphic to nG. Thus, by Proposition 5, for any graph G there is a
balanced d -magic graph which contains an induced subgraph isomorphic
to nG for all integers n > 1.
We end this section with a similar result for supermagic regular graphs.
Theorem 11. For any graph G there is a supermagic regular graph which
contains an induced subgraph isomorphic to nG for all integers n > 1.
Proof. Let G1 be a graph obtained from G by attaching a pendant edge
at each vertex of G. For any integer n > 1 and t ∈ {1, 2, . . . , n}. Let
Gt(Gt
1) be the tth copy of a graph G(G1). Put m := |V (Gt)| and denote
the vertices of Gt
1 by ut1, u
t
2, . . . , u
t
m, wt
1, w
t
2, . . . , w
t
m in such a way that
V (Gt) = {ut1, . . . , u
t
m} and utiw
t
i , for all i ∈ {1, . . . ,m}, is an attached
edge of Gt
1. Consider a mapping ξ from V (nG1) into positive integers
given by
ξ(uti) = 4 and ξ(wt
i) = 4(1 + ∆− degGt(uti))
for all i ∈ {1, . . . ,m} and t ∈ {1, 2, . . . , n}, where ∆ is the maximum
degree of Gt. Let H1 := (nG1)
ξ. By Proposition 5, H1 is a balanced
d -magic graph.
We set
U :=
n
⋃
t=1
m
⋃
i=1
ξ(ut
i
)
⋃
j=1
{(uti, j)} and W :=
n
⋃
t=1
m
⋃
i=1
ξ(wt
i
)
⋃
j=1
{(wt
i , j)}.
It is clear that U ∩ W = ∅ and U ∪ W = V (H1). The set W is an
independent set of H1 and |W | = 4nh, where h =
∑m
i=1(1+∆−degGt(uti))
for any t ∈ {1, 2, . . . , n}. Consider h, we have
h = m+
m
∑
i=1
(∆− degGt(uti)) > m > ∆.
Moreover, h = (1+∆)m−
∑m
i=1 degGt(uti) = (1+∆)m− 2|E(Gt)|. Thus,
if ∆ is odd, then h is even. Since h > ∆ and both of h,∆ are not odd, there
is a ∆-regular graph R order h. According to Proposition 5, (nR)[D4] is
balanced d -magic, 4∆-regular graph of order 4nh. Therefore, there is a
balanced d -magic graph H2, 4∆-regular graph, such that V (H2) = W .
Let H denote the graph such that the graphs H1 and H2 form its
decomposition. As H1 and H2 are balanced d -magic, by Theorem 6, the
“adm-n3” — 2019/10/20 — 9:35 — page 118 — #120
118 On the existence of degree-magic labellings
graph H is balanced d -magic. Clearly, any vertex of U has degree 4(1+∆)
in H1. Similarly, the degree of any vertex belonging to W is 4 in H1 and 4∆
in H2. So, H is a regular graph of degree 4(1+∆). According to Theorem
2, the graph H is supermagic. Therefore, H is a desired graph because its
subgraph induced by
⋃n
t=1
⋃m
i=1{(u
t
i, 1)} is isomorphic to nG.
Example 2. Considering a path P2, we can construct a supermagic
regular graph H which contains an induced subgraph isomorphic to 3P2
(see Figure 3), and the labels on edges utiv
t
j , v
t
ix
t
j , x
t
iy
t
j and utiy
t
j of H , where
1 6 i 6 4, 1 6 j 6 4 and 1 6 t 6 3, are shown in Table 3.
Figure 3. A supermagic regular graph H containing an induced subgraph
isomorphic to 3P2.
4. The n-tuple magic rectangles
In this section we introduce n-tuple magic rectangles and obtain a
sufficient condition for even n-tuple magic rectangles to exist.
Definition 1. An n-tuple magic (p, q)-rectangle R := (r1i,j)(r
2
i,j) . . . (r
n
i,j)
is a class of n arrays in which each array has p rows and q columns, and
the first npq positive integers are placed such that the sum over each row of
any array of R is constant and the sum over each column of R is another
(different if p 6= q) constant.
Let R be an n-tuple magic (p, q)-rectangle. Since each row sum of any
array of R is q(npq+1)/2 and each column sum of R is p(npq+1)/2 and
both are integer, we have
“adm-n3” — 2019/10/20 — 9:35 — page 119 — #121
P. Inpoonjai, T. Jiarasuksakun 119
Table 3. The labels on edges of supermagic regular graph H.
Vertices u11 u12 u13 u14 x11 x12 x13 x14
v11 49 54 139 144 73 80 117 116
v12 56 51 142 137 78 75 114 119
v13 141 138 52 55 115 118 76 77
v14 140 143 53 50 120 113 79 74
y11 1 6 187 192 25 30 163 168
y12 8 3 190 185 32 27 166 161
y13 189 186 4 7 165 162 28 31
y14 188 191 5 2 164 167 29 26
Vertices u21 u22 u23 u24 x21 x22 x23 x24
v21 65 70 123 128 89 96 101 100
v22 72 67 126 121 94 91 98 103
v23 125 122 68 71 99 102 92 93
v24 124 127 69 66 104 97 95 90
y21 17 22 171 176 41 46 147 152
y22 24 19 174 169 48 43 150 145
y23 173 170 20 23 149 146 44 47
y24 172 175 21 18 148 151 45 42
Vertices u31 u32 u33 u34 x31 x32 x33 x34
v31 129 134 59 64 105 112 85 84
v32 136 131 62 57 110 107 82 87
v33 61 58 132 135 83 86 108 109
v34 60 63 133 130 88 81 111 106
y31 177 182 11 16 153 158 35 40
y32 184 179 14 9 160 155 38 33
y33 13 10 180 183 37 34 156 159
y34 12 15 181 178 36 39 157 154
“adm-n3” — 2019/10/20 — 9:35 — page 120 — #122
120 On the existence of degree-magic labellings
Proposition 6. If R is an n-tuple magic (p, q)-rectangle, then the follow-
ing conditions hold:
(i) if n is odd, then p ≡ q (mod 2);
(ii) if n is even, then p ≡ q ≡ 0 (mod 2).
Proposition 6 allows the set of n-tuple magic rectangles to be divided
into sets of odd and even rectangles. We quickly see that an n-tuple magic
(2, 2)-rectangle does not exist, because the row sums and column sums of
any array are different.
Theorem 12. For any integer n > 1 and even integers p, q > 1, let
Kt
p,q be the tth copy of Kp,q for all t ∈ {1, 2, . . . , n}. A mapping f from
E(nKp,q) into positive integers given by
f(utiv
t
j) = rti,j for every utiv
t
j ∈ E(Kt
p,q),
is a d-magic labelling of nKp,q if and only if R := (r1i,j)(r
2
i,j) . . . (r
n
i,j) is
an n-tuple magic (p, q)-rectangle.
Proof. Let U t = {ut1, u
t
2, . . . , u
t
p} and V t = {vt1, v
t
2, . . . , v
t
q} be partite sets
of Kt
p,q. Suppose that R is an n-tuple magic (p, q)-rectangle. It is easy
to see that the map f : E(nKp,q) → {1, 2, . . . , npq} is bijective. For any
uti ∈ U t, we have
f∗(uti) =
q
∑
j=1
f(utiv
t
j) =
q
∑
j=1
rti,j =
q(npq + 1)
2
=
npq + 1
2
deg(uti),
and for any vtj ∈ V t, we have
f∗(vtj) =
p
∑
i=1
f(utiv
t
j) =
p
∑
i=1
rti,j =
p(npq + 1)
2
=
npq + 1
2
deg(vtj).
i.e., f is a d -magic labelling of nKp,q.
Now suppose that f is a d -magic labelling of nKp,q. For all 1 6 i 6=
s 6 p, we have
q
∑
j=1
rti,j =
q
∑
j=1
f(utiv
t
j) = f∗(uti) = f∗(uts) =
q
∑
j=1
f(utsv
t
j) =
q
∑
j=1
rts,j . (1)
For all 1 6 j 6= z 6 q, we have
p
∑
i=1
rti,j =
p
∑
i=1
f(utiv
t
j) = f∗(vtj) = f∗(vtz) =
p
∑
i=1
f(utiv
t
z) =
p
∑
i=1
rti,z. (2)
“adm-n3” — 2019/10/20 — 9:35 — page 121 — #123
P. Inpoonjai, T. Jiarasuksakun 121
By (1), we have
q
∑
j=1
rti,j =
q
∑
j=1
rts,j =
q(npq + 1)
2
.
By (2), we have
p
∑
i=1
rti,j =
p
∑
i=1
rti,z =
p(npq + 1)
2
.
Therefore, R is an n-tuple magic (p, q)-rectangle.
According to Proposition 3 and Theorem 12, we obtain the following
result.
Proposition 7. Let p and q be even positive integers with (p, q) 6= (2, 2).
Then an n-tuple magic (p, q)-rectangle exists.
References
[1] J. Sedláček, Theory of graphs and its applications, in: Problem 27, Proc. Symp.
Smolenice, Praha, 1963, pp. 163-164.
[2] B.M. Stewart, Magic graphs, Canad. J. Math., Vol. 18, 1966, pp. 1031-1059.
[3] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., Vol. 16,
2009, #DS6.
[4] L’. Bezegová, J. Ivančo, An extension of regular supermagic graphs, Discrete Math.,
Vol. 310, 2010, pp. 3571-3578.
[5] L’. Bezegová, J. Ivančo, A characterization of complete tripartite degree-magic
graphs, Discuss. Math. Graph Theory, Vol. 32, 2012, pp. 243-253.
[6] L’. Bezegová, J. Ivančo, On conservative and supermagic graphs, Discrete Math.,
Vol. 311, 2011, pp. 2428-2436.
[7] L’. Bezegová, J. Ivančo, Number of edges in degree-magic graphs, Discrete Math.,
Vol. 313, 2013, pp. 1349-1357.
[8] L’. Bezegová, Balanced degree-magic complements of bipartite graphs, Discrete
Math., Vol. 313, 2013, pp. 1918-1923.
[9] T. Harmuth, Über magische Quadrate und ähniche Zahlenfiguren, Arch. Math.
Phys., Vol. 66, 1881, pp. 286-313.
[10] T. Harmuth, Über magische Rechtecke mit ungeraden Seitenzahlen, Arch. Math.
Phys., Vol. 66, 1881, pp. 413-447.
[11] R. Sun, Existence of magic rectangles, Nei Mongol Daxue Xuebao Ziran Kexue,
Vol. 21, No. 1, 1990, pp. 10-16.
[12] T. Bier, G. Rogers, Balanced Magic Rectangles, European J. Combin., Vol. 14,
1993, pp. 285-299.
“adm-n3” — 2019/10/20 — 9:35 — page 122 — #124
122 On the existence of degree-magic labellings
[13] T. Bier, A. Kleinschmidt, Centrally symmetric and magic rectangles, Discrete
Math., Vol. 176, 1997, pp. 29-42.
[14] T.R. Hagedorn, Magic rectangles revisited, Discrete Math., Vol. 207, 1999, pp.
65-72.
[15] T.R. Hagedorn, On the existence of magic n-dimensional rectangles, Discrete
Math., Vol. 207, 1999, pp. 53-63.
Contact information
P. Inpoonjai Faculty of Sciences and Agricultural
Technology, Rajamangala University of
Technology Lanna Chiangrai, 99, Sai Khao,
Phan District, Chiang Rai, 57120, Thailand
E-Mail(s): phaisatcha_in@outlook.com
T. Jiarasuksakun Department of Mathematics, Faculty of Science,
King Mongkut’s University of Technology
Thonburi, 126 Pracha Uthit Rd., Bang Mod,
Thung Khru, Bangkok 10140, Thailand
E-Mail(s): thiradet.jia@kmutt.ac.th
Received by the editors: 28.12.2016
and in final form 07.03.2017.
|
| id | nasplib_isofts_kiev_ua-123456789-188480 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-02T00:31:08Z |
| publishDate | 2019 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Inpoonjai, P. Jiarasuksakun, T. 2023-03-02T15:26:44Z 2023-03-02T15:26:44Z 2019 On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs / P. Inpoonjai, T. Jiarasuksakun // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 107–122. — Бібліогр.: 15 назв. — англ. 1726-3255 2010 MSC: Primary 05C78; Secondary 05B15. https://nasplib.isofts.kiev.ua/handle/123456789/188480 Magic rectangles are a classical generalization of the well-known magic squares, and they are related to graphs. A graph G is called degree-magic if there exists a labelling of the edges by integers 1, 2, . . . , |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1 + |E(G)|) deg(v)/2. Degree-magic graphs extend supermagic regular graphs. In this paper, we present a general proof of the necessary and sufficient conditions for the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs. We apply this existence to construct supermagic regular graphs and to identify the sufficient condition for even n-tuple magic rectangles to exist. The authors would like to thank the anonymous referee for careful reading and the helpful comments improving this paper. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs Article published earlier |
| spellingShingle | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs Inpoonjai, P. Jiarasuksakun, T. |
| title | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| title_full | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| title_fullStr | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| title_full_unstemmed | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| title_short | On the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| title_sort | on the existence of degree-magic labellings of the n-fold self-union of complete bipartite graphs |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/188480 |
| work_keys_str_mv | AT inpoonjaip ontheexistenceofdegreemagiclabellingsofthenfoldselfunionofcompletebipartitegraphs AT jiarasuksakunt ontheexistenceofdegreemagiclabellingsofthenfoldselfunionofcompletebipartitegraphs |