# Tree-Antimagicness of Disconnected Graphs

Authors: Martin Bača; Zuzana Kimáková; Andrea Semaničová-Feňovčíková; Muhammad Awais Umar
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A simple graphG admits an H-covering if every edge in E
(
G
) belongs to a subgraph of G isomorphic to H. The graph G is said to be (a, d)-H-antimagic if there exists a bijection from the vertex set V
(
G
) and the edge set E
(
G
) onto the set of integers 1
,
2
,
…
,
V
G
+
E
(
G
) such that, for all subgraphs H
′ of G isomorphic to H, the sum of labels of all vertices and edges belonging to H
′ constitute the arithmetic progression with the initial term a and the common difference d. G is said to be a super (a, d)-H-antimagic if the smallest possible labels appear on the vertices. In this paper, we study super tree-antimagic total labelings of disjoint union of graphs.


---

## Body

## 1. Introduction

We consider finite undirected graphs without loops and multiple edges. The vertex and edge set of a graphG are denoted by V
(
G
) and E
(
G
), respectively. Anedge-covering of G is a family of subgraphs H
1
,
H
2
,
…
,
H
t such that each edge of E
(
G
) belongs to at least one of the subgraphs H
i, i
=
1,2
,
…
,
t. In this case we say that G admits an (
H
1
,
H
2
,
…
,
H
t
)
-(edge) covering. If every subgraph H
i is isomorphic to given graph H, then the graph G admits an H
-covering. A bijective function f
:
V
(
G
)
∪
E
(
G
)
→
{
1,2
,
…
,
V
(
G
)
+
E
(
G
)
} which we call atotal labeling and the associated H-weight of subgraph H is w
t
f
(
H
)
=
∑
v
∈
V
(
H
)
f
(
v
)
+
∑
e
∈
E
(
H
)
f
(
e
). An (
a
,
d
)-H
-antimagic total labeling of graph G admitting an H-covering is a total labeling with the property that, for all subgraphs H
′ isomorphic to H, the H
′-weights form an arithmetic progression a
,
a
+
d
,
a
+
2
d
,
…
,
a
+
(
t
-
1
)
d, where a
>
0 and d
≥
0 are two integers and t is the number of all subgraphs of G isomorphic to H. Such a labeling is called asuper if the smallest possible labels appear on the vertices. A graph that admits a (super) (
a
,
d
)-H-antimagic total labeling is called a(super)
(
a
,
d
)-H
-antimagic. For d
=
0, it is called H-magic and H-supermagic, respectively.TheH-(super)magic labelings were first studied by Gutiérrez and Lladó [1]. These labelings are the generalization of the edge-magic and super edge-magic labelings that were introduced by Kotzig and Rosa [2] and Enomoto et al. [3], respectively. For further information about (super) edge-magic labelings, one can see [4–8]. Gutiérrez and Lladó [1] proved that certain classes of connected graphs are H-(super)magic, such as the star K
1
,
n and the complete bipartite graphs K
n
,
m are K
1
,
h-supermagic for some h. They also proved that the cycle C
n is P
h-supermagic for any 2
≤
h
≤
n
-
1 such that gcd
(
n
,
h
(
h
-
1
)
)
=
1. Lladó and Moragas [9] studied the cycle-(super)magic behavior of several classes of connected graphs. They proved that wheels, windmills, books, and prisms are C
h-magic for some h. Maryati et al. [10] and also Salman et al. [11] proved that certain families of trees are path-supermagic. Ngurah et al. [12] proved that chains, wheels, triangles, ladders, and grids are cycle-supermagic.The(
a
,
d
)-H-antimagic total labeling is introduced by Inayah et al. [13]. In [14], the super (
a
,
d
)-H-antimagic labelings are investigated for some shackles of connected graph H.WhenH is isomorphic to K
2, a super (
a
,
d
)-K
2-antimagic total labeling is also called super (
a
,
d
)-edge-antimagic total. The notion of (
a
,
d
)-edge-antimagic total labeling was introduced by Simanjuntak et al. in [15] as a natural extension of theedge-magic labeling defined by Kotzig and Rosa in [2] asmagic valuation.The (super)(
a
,
d
)-H-antimagic total labeling is related to a super d-antimagic labeling of type (
1,1
,
0
) of a plane graph. A labeling of type (
1,1
,
0
), that is, a total labeling, of a plane graph is said to be d
-antimagic if for every positive integer s the set of weights of all s-sided faces is W
s
=
{
a
s
,
a
s
+
d
,
a
s
+
2
d
,
…
,
a
s
+
(
f
s
-
1
)
d
} for some integers a
s
>
0 and d
≥
0, where f
s is the number of the s-sided faces. Note that there are allowed different sets W
s for different s. Theweight of a face under a labeling of type (
1,1
,
0
) is the sum of labels of all the edges and vertices surrounding that face. If d
=
0, then Lih [16] calls such labelingmagic and describes magic (0-antimagic) labelings of type (
1,1
,
0
) for wheels, friendship graphs, and prisms. In [17], Ahmad et al. investigate the existence of super d-antimagic labelings of type (
1,1
,
0
) for disjoint union of plane graphs for several values of difference d.In this paper we mainly investigate the existence of super(
a
,
1
)-tree-antimagic total labelings for disconnected graphs. We concentrate on the following problem: if graph G admits a (super) (
a
,
1
)-tree-antimagic total labeling, does the disjoint union of m copies of the graph G, denoted by m
G, admit a (super) (
b
,
1
)-tree-antimagic total labeling as well?


## 2. Super(
a
,
1
)-Tree-Antimagic Total Labeling

In this section, we will study the super(
a
,
1
)-tree-antimagicness for disconnected graphs. The main result is the following.Theorem 1.
Letm
,
t
≥
1 be positive integers. Let G
i with a (
T
i
1
,
T
i
2
,
…
,
T
i
t
)-covering be a super (
a
,
1
)-T-antimagic graph of order p and size q, i
=
1,2
,
…
,
m, where T is a tree and every tree T
i
j, j
=
1,2
,
…
,
t, is isomorphic to T. Then the disjoint union ⋃
i
=
1
m
‍
G
i is also a super (
b
,
1
)-T-antimagic graph.Proof.
Letm
≥
1 and t
≥
1 be positive integers and let T be a tree of order k. Let G
i, i
=
1,2
,
…
,
m, be a graph with p vertices and q edges that admits a (
T
i
1
,
T
i
2
,
…
,
T
i
t
)-covering. Note that G
i is not necessarily isomorphic to G
j for i
≠
j. Assume that every G
i, i
=
1,2
,
…
,
m, has a super (
a
,
1
)-T-antimagic total labeling f
i
:
V
(
G
i
)
∪
E
(
G
i
)
→
{
1,2
,
…
,
p
}
∪
{
p
+
1
,
p
+
2
,
…
,
p
+
q
}; thus
(1)
{
w
t
f
i
(
T
i
j
)
:
j
=
1,2
,
…
,
t
}
=
{
a
,
a
+
1
,
…
,
a
+
t
-
1
}
is the set of the corresponding T
i
j-weights, where every tree T
i
j, j
=
1,2
,
…
,
t, is isomorphic to T.
Define the labelingf for the vertices and edges of ⋃
i
=
1
m
‍
G
i in the following way:
(2)
f
(
x
)
=
m
f
i
x
-
1
+
i
,
if
x
∈
V
(
G
i
)
,
m
f
i
x
+
1
-
i
,
if
x
∈
E
(
G
i
)
.
First we will show that the vertices of ⋃
i
=
1
m
‍
G
i under the labeling f, use integers from 1 up to p
m; that is, if i
=
1, then the vertices of G
1 successively attain values [
1
,
m
+
1,2
m
+
1
,
…
,
(
p
-
1
)
m
+
1
], if i
=
2, then the vertices of G
2 successively assume values [
2
,
m
+
2,2
m
+
2
,
…
,
(
p
-
1
)
m
+
2
]
,
…, the values of vertices of G
i are equal successively to [
i
,
m
+
i
,
2
m
+
i
,
…
,
(
p
-
1
)
m
+
i
]
,
…, and if i
=
m, then the vertices of G
m successively assume values [
m
,
2
m
,
3
m
,
…
,
p
m
].
Second we can see that the edges of⋃
i
=
1
m
‍
G
i under the labeling f use integers from p
m
+
1 up to (
p
+
q
)
m. It means that if i
=
1, then the edges of G
1 successively assume values [
(
p
+
1
)
m
,
(
p
+
2
)
m
,
(
p
+
3
)
m
,
…
,
(
p
+
q
)
m
], if i
=
2, then the edges of G
2 successively attain values [
(
p
+
1
)
m
-
1
,
(
p
+
2
)
m
-
1, (
p
+
3
)
m
-
1
,
…
,
(
p
+
q
)
m
-
1
]
,
…, the values of edges of G
i are equal successively to [
(
p
+
1
)
m
+
1
-
i, (
p
+
2
)
m
+
1
-
i, (
p
+
3
)
m
+
1
-
i
,
…
,
(
p
+
q
)
m
+
1
-
i
]
,
…, and if i
=
m, then the edges of G
m successively attain values [
p
m
+
1
,
(
p
+
1
)
m
+
1, (
p
+
2
)
m
+
1
,
…
,
(
p
+
q
-
1
)
m
+
1
].
It is not difficult to see that the labelingf is a bijective function which assigns the integer {
1,2
,
…
,
(
p
+
q
)
m
} to the vertices and edges of ⋃
i
=
1
m
‍
G
i; thus f is a total labeling.
For the weight of every subgraphT
i
j isomorphic to the tree T under the labeling f, we have
(3)
w
t
f
T
i
j
=
∑
v
∈
V
(
T
i
j
)
‍
f
(
v
)
+
∑
e
∈
E
(
T
i
j
)
‍
f
(
e
)
=
∑
v
∈
V
(
T
i
j
)
‍
m
(
f
i
(
v
)
-
1
)
+
i
+
∑
e
∈
E
(
T
i
j
)
‍
m
f
i
(
e
)
+
1
-
i
=
m
∑
v
∈
V
(
T
i
j
)
‍
f
i
(
v
)
-
m
V
(
T
i
j
)
+
i
V
(
T
i
j
)
+
m
∑
e
∈
E
(
T
i
j
)
‍
f
i
(
e
)
+
E
(
T
i
j
)
-
i
E
(
T
i
j
)
=
m
∑
v
∈
V
T
i
j
‍
f
i
v
+
∑
e
∈
E
T
i
j
‍
f
i
e
-
m
V
(
T
i
j
)
+
E
(
T
i
j
)
+
i
V
T
i
j
-
i
E
T
i
j
=
m
w
t
f
i
(
T
i
j
)
-
m
V
(
T
i
j
)
+
E
(
T
i
j
)
+
i
V
(
T
i
j
)
-
i
E
(
T
i
j
)
.
As every T
i
j, i
=
1,2
,
…
,
m, j
=
1,2
,
…
,
t, is isomorphic to the tree T, it holds
(4)
V
(
T
i
j
)
=
V
(
T
)
=
k
,
E
(
T
i
j
)
=
E
(
T
)
=
V
(
T
)
-
1
=
k
-
1
.
Thus for the T-weights we get
(5)
w
t
f
(
T
i
j
)
=
m
w
t
f
i
(
T
i
j
)
+
k
(
1
-
m
)
-
1
+
i
.
According to (1), we get that the T-weights in components are the following:ifi
=
1, then the T
1
j-weights in G
1 are m
(
a
-
k
)
+
k, m
(
a
-
k
+
1
)
+
k
,
…, and m
(
a
-
k
+
t
-
1
)
+
k;
ifi
=
2, then the T
2
j-weights in G
2 are m
(
a
-
k
)
+
k
+
1, m
(
a
-
k
+
1
)
+
k
+
1
,
…, and m
(
a
-
k
+
t
-
1
)
+
k
+
1;
ifi
=
3, then the T
3
j-weights in G
3 are m
(
a
-
k
)
+
k
+
2, m
(
a
-
k
+
1
)
+
k
+
2
,
…, and m
(
a
-
k
+
t
-
1
)
+
k
+
2;
⋮
ifi
=
m
-
1, then the T
m
-
1
j-weights in G
m
-
1 successively attain values m
(
a
-
k
)
+
k
+
m
-
2, m
(
a
-
k
+
1
)
+
k
+
m
-
2, …, and m
(
a
-
k
+
t
-
1
) +
k
+
m
-
2;
ifi
=
m, then the T
m
j-weights in G
m successively assume values m
(
a
-
k
)
+
k
+
m
-
1, m
(
a
-
k
+
1
)
+
k
+
m
-
1, …, and m
(
a
-
k
+
t
-
1
) +
k
+
m
-
1.
It is easy to see that the set of allT-weights in ⋃
i
=
1
m
‍
G
i consists of distinct and consecutive integers:
(6)
w
t
f
T
i
j
:
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
t
=
m
a
-
k
+
k
,
m
a
-
k
+
k
+
1
,
…
,
m
(
a
-
k
+
t
)
+
k
-
1
.
Thus the graph⋃
i
=
1
m
‍
G
i is a super (
m
(
a
-
k
)
+
k
,
1
)-T-antimagic.Immediately from the previous theorem we get that arbitrary number of copies of a super(
a
,
1
)-T-antimagic graph is a super (
b
,
1
)-T-antimagic.Corollary 2.
LetG be a super (
a
,
1
)-T-antimagic graph, where T is a tree. Then the disjoint union of arbitrary number of copies of G, that is, m
G, m
≥
1, also admits a super (
b
,
1
)-T-antimagic total labeling.Moreover, form copies of a graph G which is (
a
,
1
)-T-antimagic but is not super, we can derive the following result.Theorem 3.
LetG be an (
a
,
1
)-T-antimagic graph of order p and size q, where T is a tree. Then m
G, m
≥
1, is also a (
b
,
1
)-T-antimagic graph.Proof.
LetT be a tree of order k and let G be an (
a
,
1
)-T-antimagic graph of order p and size q with corresponding labeling f
:
V
(
G
)
∪
E
(
G
)
→
{
1,2
,
…
,
p
+
q
} and the corresponding T-weights a
,
a
+
1
,
a
+
2
,
…
,
a
+
t
-
1.
For every vertexv in G, we denote by symbol v
i the corresponding vertex in the ith copy of G in m
G. Analogously, let u
i
v
i be the edge corresponding to the edge u
v in the ith copy of G in m
G.
Form
≥
1, we define labeling g of m
G as follows:
(7)
g
(
v
i
)
=
m
(
f
(
v
)
-
1
)
+
i
for
v
∈
V
(
G
)
,
i
=
1,2
,
…
,
m
,
g
(
u
i
v
i
)
=
m
f
(
u
v
)
+
1
-
i
for
u
v
∈
E
(
G
)
,
i
=
1,2
,
…
,
m
.
Letr
∈
{
1,2
,
…
,
p
+
q
}. We consider two cases.
Case 1. If the number r is assigned by the labeling f to a vertex of G, then the corresponding vertices v
i, i
=
1,2
,
…
,
m, in the copies G
i in m
G will receive labels
(8)
{
g
v
i
:
g
v
i
=
m
(
r
-
1
)
+
i
,
i
=
1,2
,
…
,
m
}
=
m
r
-
1
+
1
,
m
r
-
1
+
2
,
…
,
m
r
.
Case 2. If the number r is assigned by the labeling f to an edge of G, then the corresponding edges u
i
v
i, i
=
1,2
,
…
,
m, in the copies G
i in m
G will have labels
(9)
{
g
(
u
i
v
i
)
:
g
(
u
i
v
i
)
=
m
r
+
1
-
i
,
i
=
1,2
,
…
,
m
}
=
{
m
r
,
m
r
-
1
,
…
,
m
(
r
-
1
)
+
1
}
.
We can see that the vertex labels and edge labels in m
G are not overlapping, and the maximum used label is m
(
p
+
q
). Thus g is a total labeling.
Analogously as in the proof of Theorem1 we get that the weight of every subgraph T
i
j, i
=
1,2
,
…
,
m, j
=
1,2
,
…
,
t, under the labeling g attains the value
(10)
w
t
g
T
i
j
=
∑
v
∈
V
(
T
i
j
)
‍
g
(
v
)
+
∑
u
v
∈
E
(
T
i
j
)
‍
g
(
u
v
)
=
∑
v
∈
V
(
T
i
j
)
‍
m
(
f
(
v
)
-
1
)
+
i
+
∑
u
v
∈
E
T
i
j
‍
m
f
u
v
+
1
-
i
=
m
w
t
f
(
T
i
j
)
+
k
(
1
-
m
)
-
1
+
i
and the set of all T-weights in m
G successively attain consecutive values m
(
a
-
k
)
+
k
,
m
(
a
-
k
)
+
k
+
1
,
…
,
m
(
a
-
k
+
t
)
+
k
-
1. Thus the resulting labeling g is a (
b
,
1
)-T-antimagic total labeling.


## 3. Disjoint Union of Certain Families of Graphs

In [18], the following results are proved on path-antimagicness of cycles and paths.Proposition 4 (see [18]).
Letk and n
≥
3 be positive integers. The cycle C
n is a super (
a
,
1
)-P
k-antimagic for every k
=
2,3
,
…
,
n.Proposition 5 (see [18]).
Letk and n
≥
3 be positive integers. The path P
n is a super (
a
,
1
)-P
k-antimagic for every k
=
2,3
,
…
,
n.In light of Propositions4 and 5 and Corollary 2 we immediately obtain the following.Corollary 6.
Letk, m
≥
1, and n
≥
3 be positive integers. Then m copy of a cycle C
n, that is, the graph m
C
n, is a super (
a
,
1
)-P
k-antimagic for every k
=
2,3
,
…
,
n.Corollary 7.
Letk, m
≥
1, and n
≥
3 be positive integers. Then m copy of a path P
n, that is, the graph m
P
n, is a super (
a
,
1
)-P
k-antimagic for every k
=
2,3
,
…
,
n.


## 4. Conclusion

In this paper we have shown that the disjoint union of multiple copies of a (super)(
a
,
1
)-tree-antimagic graph is also a (super) (
b
,
1
)-tree-antimagic. It is a natural question whether the similar result holds also for other differences and other H-antimagic graphs. For further investigation we propose the following open problems.Open Problem 1. Let G be a (super) (
a
,
d
)-T-antimagic graph, where T is a tree different from K
2. For the graph m
G, determine if there is a (super) (
a
,
d
)-T-antimagic total labeling, for d
≠
1 and all m
≥
1.Open Problem 2. Let G be a (super) (
a
,
d
)-H-antimagic graph. For the graph m
G, determine if there is a (super) (
a
,
d
)-H-antimagic total labeling, for certain values of d and all m
≥
1.



---

*Source: 504251-2015-01-15.xml*