Applied Mathematics, 2011, 2, 1393-1396
doi:10.4236/am.2011.211197 Published Online November 2011 (http://www.SciRP.org/journal/am)
New Constructions of Edge Bimagic Graphs from
Magic Graphs
Jayapal Baskar Babujee, Babitha Suresh
Department of Mat hematics, Anna University, Chennai, India
Received September 5, 2011; revised Oct o ber 14, 2011; accepted Octob er 21, 2011
Abstract
An edge magic total labeling of a graph G(V,E) with p vertices and q edges is a bijection f from the set of
vertices and edges to such that for every edge uv in E, f(u) + f(uv) + f(v) is a constant k. If there
exist two constants k1 and k2 such that the above sum is either k1 or k2, it is said to be an edge bimagic total
labeling. A total edge magic (edge bimagic) graph is called a super edge magic (super edge bimagic) if
f(V(G)) = . In this paper we define super edge edge-magic labeling and exhibit some interesting
constructions related to Edge bimagic total labeling.
1, 2,,pq

1, 2,,p
Keywords: Graph, Labeling, Magic Labeling, Bimagic Labeling, Function
1. Introduction
A labeling of a graph G is an assignment f of labels to
either the vertices or the edges or both subject to certain
conditions. Labe led graphs are becoming an increasingly
useful family of Mathematical Models from a broad
range of applications. Graph labeling was first intro-
duced in the late 1960 ’s. A useful survey on graph label-
ing by J. A. Gallian (2010) can be found in [1]. All
graphs considered here are finite, simple and undirected.
We follow the notation and terminology of [2]. In most
applications labels are po sitive (or nonnegative) integers,
though in general real numbers could be used. A (p,
q)-graph with p vertices an d q edges is called
total edge magic if there is a bijection
such that there exists a constant k for any
edge uv in E,
(,)GVE
}pq:fV E {1, 2,,
() () ().
f
ufuvfvk
((
The original
concept of total edge-magic graph is due to Kotzig and
Rosa [3 ]. They called it magic graph. A total edge-magic
graph is called a super edge-magic i f )){1,2,, }
f
VG p.
Wallis [4] called super edge-magic as strongly edge-
magic. An Edge antimagic total labeling of a graph with
p vertices and q edges is a bijection from the set of edges
to such that the sums of the label of the
edge and incident vertices are pairwise distinct.
1, 2,,pq
It becomes interesting when we arrive with magic type
labeling summing to exactly two distinct constants say
or Edge bimagic totally labeling was introduced
by J. Baskar Babuje e [5] and studied in [6] as (1,1) ed ge
1
k2.k
bimagic labeling. A graph with p vertices and
q edges is called total edge bimagic if there exists a bi-
jection
(,)Gpq
1,2,,:{ }.
f
VE
,uv Epq such that for any edge

we have two constants 1 and 2 with
12
k k
()()() or .
f
ufvfuvk k

 A total edge-bimagic
graph is called super edge-bimagic if (()), ,}{1,2
f
VG p

.
Super edge-bimagic labeling for path, star-1,1, ,nnn
are proved in [7]. Super edge-bimagic labeling for cycles,
Wheel graph, Fan graph, Gear graph, Maximal Planar
class-Pln:
,KK
5,n
1, 1, 11,
(, 1),( 2),,
mnnn mn
K
Kmn PPnPK


31,22 12
( 1),(3),)(
nn
CKnPNnPmKN 1),m
(3, n)-kite graph


2,n are proved in [8-10]. In this
paper we define super edge edge-magic and exhibit some
interesting constructions related to Edge bimagic total
labeling. For our convenience, we state total edge-magic
as edge-magic total labeling throughout the paper.
2. Main Results
On renaming Super edge-magic as Super vertex edge-
magic it motivates us to define super edge edge-magic
labeling in graphs.
Definition 2.1 A graph with p vertices
and q edges is called total edge magic if there is a
bijection function
(,)GVE
:{1,2,,}
f
VE pq  such that

J. B. BABUJEE ET AL. 1394
for any edge uv in E we have a constant k with
() () ().
f
ufuvfvk A total edge-magic graph is
called super edge edge-magic if (()) {1,2,,}.
f
EG q
1
)q(,)Gpq
2
2
ôGGG
q
:{1,2,,
Next we introduce a definition for vertex superim-
posing between two grap hs.
Definition 2.2 If and 222 are
two connected graphs, 1 is obtained by superim-
posing any selected vertex of on any selected vertex
of The resultant graph 1 consists of
vertices and edges.
11
(,Gp
2
ôGG
G
q
1.G1pp
ôn GP
12 12
Theorems 2.3 If G has super edge edge-magic total
labeling then, admits edge bimagic total labeling.
Proof: Let G(p, q) be super edge edge-magic graph
with the bijective function }
f
VE pq 
1
.
such that()()()
f
ufuvfv kwV. Let be the
vertex whose label ()
f
wpq is the maximum
value. Consider the path Pn with vertex set
{:1 }
i
x
in
wV
ôn GGP

{:2 }
i
VV xin  
{, :2
ii
EEwxxx

 gV

,, 2pqn pq n 
and edge set 1 {: We
superimpose one of th e pendent vertex of the path Pn say
x1 on the vertex of G. Now we define the new
graph called with vertex set
and
1 1}.
ii
xxi n
 
1}. 
{1,2,,, 1, p qpq 
() ()
21 Consider the bijec-
tive function
defined by
in 
:' E
2}
,

g
vfv

for all and
vV()()
g
uv
() (
f uv.uv E
G
() .
for all
From our construction of new graph ,
1)
f
wgx gwpq
2 , even
22
For 2, ()



 




i
in
gx
2
()gwx
1
( )
ii
gxxp q

1,k
() () ()
1 , odd
2
 
 




ni
pq i
i
pq i
Now
2(1p qn );
21 for 21.n iin 
Since the graph G is super edge edge-magic with
common count implies that
1
g
uguvgvk
{, :21
ii
wxx xin

for all Now we have
to prove that the remaining edges in the set
have the common count k2.
.uv E
21
For the edge wx2, }
22
2
() ()
22
332
gw gwx
pqpq
pq



( )
+
2
2
2
gx
n
n pq
n
n k

 



 


For any edge xixi+1, if i is even,
11
2
() () ()
221
22
332 2
2
iiii
gx gxxgx
ni i
pqpq nipq
n
pqn k


 
2

 






If i is odd,
11
2
() () ()
11
+21
22
=3322
2
iiii
gx gxxgx
in
pqpqnipq
n
pqn k


2
i



 



 

 
Thus ôn GGP


has two common count k1 and k2.
Hence has edge bimagic total labeling. ôn GP
Example 2.4 Taking 1,6 which is super edge
edge magic, by using the theorem 2.3, 51,65
GKôôGP KP

admits edge bimagic total labeling with two common
count k1 = 26 and k2 = 50 is given in Figure 1.
Theorem 2.5 1, is total edge bimagic for any
arbitrary super edge edge-magic Graph G.
ôn GK
Proof: Let G(p,q) be super edge edge-magic graph
with the bijective function :{1,2,,}
f
VE pq 
1
()
such that ()()
f
ufuvfvk


() wV . Let be the
vertex whose label
f
wpq is the maximum
value. Consider the star K1,n with vertex set
0i
{, :1}
x
xin

 and edge set 0 {:1}.
i
x
xin We
superimpose the vertex x0 of the star K1,n graph on the
vertex wV of G. Now we define the new graph called
1,
ôGGK
n


with vertex set and {:1 }
i
VV xin
 
{:1 }.
i
wx inEE



:{1,2,,
Consider the bijective function
, 1,,,,2}
g
VEpqpqpqnpq n


  
vV()()defined by g(v) = f(v) for all and
g
uvfuv

for all .Euv

From our construction of new graph , G
0
() () ().
f
wgx gwpq


()2(1) , for 1.
i
g
xpqniin


and (); for 1
i
g
wxpq iin

 .
Since th e graph G is super edge edge-magic with com-
mon count k1, implies that 1
() () ()
g
uguvgvk for
Figure1. Edge bimagic total labeling of K1,6ôP5.

J. B. BABUJEE ET AL.1395
all Now we have to prove that the remaining
edges joining w and
.uv E:1
i
x
in

 have the common
count k2.
For any edge wxi,
2
() () ()
2(1
3321.
ii
gw gwxgx
pqpqipqni
pqn k

 

)
}
Thus we have 1, has two common count k1
and k2. Hence has edge bimagic total labeling.
ôn GGK

ôn GK
1,
Theorem 2.6 If G has super edge edge-magic total la-
beling then, admits edge bimagic total labeling.
1,
Proof: Let G(p,q) be super edge edge-magic graph
with the bijective function
ôn GF
:{1,2,,
f
VE pq 
()
such that 1
()()
f
ufuv
() fvkwV . Let be the
vertex whose label
f
wpq
0
{, :1}
i
is the maximum value.
Consider the Fan F1,n with vertex set
x
xin


}{: 11}.
iii
xx in

 
{:1 }
i
VV xin
and edge set 01 We
superimpose the vertex x0 of the Fan F1,n graph on the
vertex of G. Now we define the new graph called
with vertex set
{:1xx in
V
n
F
w
1,
ôGG


 
1
{ :11}.
iii
xx in

:'{1,2,,
and
Consi-
der the bijective function
{:1 }wx in  EE
 ,
g
VE pq
 
21,,31}qnpq n 
defined by
1, ,, ,pqn p
() ()
pq
g
vfv for all and vV()
g
uv

()
f
uv for all .uv E
From our construction of new graph G’,
0
() () ().
f
wgx gwq p
Now
15(1) 6
()1,for 1
4
i
ii
g
xpq i
 
 n.
and
1
()33, for 11;
ii
gxxp qniin
 
1275( 1)6
()1,for 1.
4
i
ini
g
wxp qin
 
 
Since the graph G is super edge edge-magic with
common count k1, implies that 1 () () ()
g
uguvgvk
1
}{ :11
iii
nx xin


for all uv E. Now we have to prove that the remaining
edges in the set {:
have the common count k2.
1wxi }
For any edge wxi,
2
()()() 1
1275( 1)615( 1)6
1
44
= 3().
ii
ii
gwgwxgxp qp q
ni
pq
pqn k

  

 
i
And for the edge xixi+1,
11
1
2
15(1) 6
() () ()14
15(1)6( 1)
33 14
3() .
i
iiii
i
i
gxgxxgxp q
i
pqnipq
pqn k


 

 
 

Thus we have 1,
ôn GGF


has two common count k1
and k2. Hence has edge bimagic total labeling.
1,n
Example 2.7 illustrates the labeling technique used in
the above theorem 2.6.
ôGF
Example 2.7 Let k1 be the constant edge count of an
arbitrary graph G(p, q) which is super edge edge-magic
with maximum label 15pq


ôGF for one of its vertex. The bimagic labeling for 1,5 with
23() 60kpqn

  can be verified from the given
Figure 2.
Theorem 2.8 If G1 has super edge edge-magic la-
beling and G2 has super vertex edge-magic labeling then,
admits edge bimagic total labeling.
12
ôGG
Proof: Let G1 be the super edge edge-magic then there
exist the b ijecti ve function 11 11
:{1,2,,}
f
VE pq 
() such that 1 ()()
f
ufuvfvk

 ,uv V for all 1

, and
Let G2 be the super vertex edge-magic then there exist
the bijective function 22 22 :{ 1, 2,, }
g
VE pq 
() such that 2 ()( )
g
uguvgvk

 ,.uv V, for all 2

Let
1
wV

be the vertex whose label is the maximum value
11
pq

and 12
x
V

be the vertex with label 1. We su-
perimpose the vertex x1 of G2 graph on the vertex 1 wV

.
Now we define the new graph called with
vertex set 12
ôGGG



1
x12 .EEE

:{1,2,, 1hV Ep q

 
1122
}pqpq
12
VV and Con-
sider the bijective function 11
V

11
, 1,,pq ,
11
pq

  defined by
1
()() for all ();hufuuVGw



1
() () for all ();h uvfuvuvEG



11
() ();hwhxpq
1


112 1
()1() for all ();hvpqgvvV Gx



11 2
()1() for all ().h uvpqguvuvEG



For the edges in G1, we hav e
1
()( )()()( )().huhuvhvf ufuvfvk

 
Figure 2. Construction of bimagic for GôF1,5.

J. B. BABUJEE ET AL. 1396
1
Since magic labeling is preserved in a graph if all the
vertices and edges are increased by any constants, for the
edges in G2, we have
11 11
11
1123
()( )()
1()
()1 ()
3( 1).
hu huv hv
pqgu pq
g
uvpqg v
pqk k

 


So has two common count k1 and k
3.
Hence admits edge bimagic total labeling.
12
ôGGG

ôGG
12
Theorem 2.9 If G has super edge edge-magic total
labeling then, G + K1 admits edge bimagic total labeling.
Proof: Let G(p,q) be super edge edge-magic. Then there
exist a bijective function function
such that 1
:{1,2fV E 
(),, }pq()( )
f
ufuv
GG
fvk
1
K. Now we de-
fine the new graph called



1 }.ip

1, ,21}
p q 
with vertex set
and Consider
the bijective function
defined as follows,
=VV

:gV
{x
E


}{:
i
EE xv

,, ,
p qp q{1,2
Since there are p vertices in the graph G,
()1 for 1
i
g
vpqi i p and
() ()
g
uvfuv for all .uv E
() 21
g
xpq and (); for 1.
i
g
xvpq iip


Since the graph G is super edge edge-magic with
common count k1, implies that 1
() () ()
g
uguvgvk.
Now we have to prove that the remaining p edges joining
V and x have the common count k2.
For any edge xvi,
2
()()( )
21
432 .
ii
gx gxvgv
pq pqipqi
pqk



1
Thus we have 1 has two common count k1
and k2. Hence has edge bimagic total labeling.
GGK
1
K

G
3. Concluding Remarks
Theorem 2.8 shows that 12 admit edge bimagic
total labeling if G1 has super edge edge-magic labeling
and G2 has super vertex edge-magic labeling. Further
investigation can be done to obtain the conditions at
which 12 admits edge bimagic total labeling for
any two arbitrary total magic gr aphs.
ôGG
ôGG
4. Acknowledgements
The referee is gratefully acknowledged for their sugges-
tions that improved the manuscript.
5. References
[1] J. A. Gallian, “A Dynamic Survey of Graph Labeling,”
Electronic Journal of Combinatorics, Vol. 17, No. 1, 2010,
pp. 1-246.
[2] N. Hartsfield and G. Ringel, “Pearls in Graph Theory,”
Academic Press, Cambridge, 1990.
[3] A. Kotzig and A. Rosa, “Magic Valuations of Finite Gra-
phs,” Canadian Ma thematical Bull etin, Vol. 13, 1970, pp.
451-461. doi:10.4153/CMB-1970-084-1
[4] W. D. Wallis, “Magic Graphs,” Birkhauser, Basel, 2001.
doi:10.1007/978-1-4612-0123-6
[5] J. B. Babujee, “Bimagic Labeling in Path Graphs,” The
Mathematics Education, Vol. 38, No. 1, 2004, pp. 12-16.
[6] J. B. Babujee, “On Edge Bimagic Labeling,” Journal of
Combinatorics Information & System Sciences, Vol. 28,
No. 1-4, 2004, pp. 239-244.
[7] J. B. Babujee and R. Jagadesh, “Super Edge Bimagic
Labeling for Trees” International Journal of Analyzing
methods of Components and Combinatorial Biology in
Mathematics, Vol. 1 No. 2, 2008, pp. 107-116.
[8] J. B. Babujee and R. Jagadesh, “Super Edge Bimagicla-
beling for Graph with Cycles,” Pacific-Asian Journal of
Mathematics, Vol. 2, No. 1-2, 2008, pp. 113-122.
[9] J. B. Babujee and R. Jagadesh, “Super Edge Bimagic La-
beling for Disconnected Graphs,” International Journal
of Applied Mathematics & Engineering Sciences, Vol. 2,
No. 2, 2008, pp. 171-175.
[10] J. B. Babujee and R. Jagadesh, “Super Edge Bimagic La-
beling for Some Class of Connected Graphs Derived from
Fundamental Graphs,” International Journal of Combina-
torial Graph Theory and Applications, Vol. 1, No. 2, 2008,
pp. 85-92.