Applied Mathematics, 2011, 2, 13931396 doi:10.4236/am.2011.211197 Published Online November 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM New Constructions of Edge Bimagic Graphs from Magic Graphs Jayapal Baskar Babujee, Babitha Suresh Department of Mat hematics, Anna University, Chennai, India Email: baskarbabujee@yahoo.com, babi_mit@yah o o.co.in 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 edgemagic 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,, () () (). ufuvfvk (( The original concept of total edgemagic graph is due to Kotzig and Rosa [3 ]. They called it magic graph. A total edgemagic graph is called a super edgemagic i f )){1,2,, } VG p. Wallis [4] called super edgemagic 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,,:{ }. VE ,uv Epq such that for any edge we have two constants 1 and 2 with 12 k k ()()() or . ufvfuvk k A total edgebimagic graph is called super edgebimagic if (()), ,}{1,2 VG p . Super edgebimagic labeling for path, star1,1, ,nnn are proved in [7]. Super edgebimagic labeling for cycles, Wheel graph, Fan graph, Gear graph, Maximal Planar classPln: ,KK 5,n 1, 1, 11, (, 1),( 2),, mnnn mn Kmn PPnPK 31,22 12 ( 1),(3),)( nn CKnPNnPmKN 1),m (3, n)kite graph 2,n are proved in [810]. In this paper we define super edge edgemagic and exhibit some interesting constructions related to Edge bimagic total labeling. For our convenience, we state total edgemagic as edgemagic total labeling throughout the paper. 2. Main Results On renaming Super edgemagic as Super vertex edge magic it motivates us to define super edge edgemagic 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,,} VE pq such that
J. B. BABUJEE ET AL. 1394 for any edge uv in E we have a constant k with () () (). ufuvfvk A total edgemagic graph is called super edge edgemagic if (()) {1,2,,}. 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 edgemagic total labeling then, admits edge bimagic total labeling. Proof: Let G(p, q) be super edge edgemagic graph with the bijective function } VE pq 1 . such that()()() ufuvfv kwV. Let be the vertex whose label () wpq is the maximum value. Consider the path Pn with vertex set {:1 } i 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} , vfv for all and vV()() uv () ( f uv.uv E G () . for all From our construction of new graph , 1) wgx gwpq 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 edgemagic with common count implies that 1 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 edgemagic Graph G. ôn GK Proof: Let G(p,q) be super edge edgemagic graph with the bijective function :{1,2,,} VE pq 1 () such that ()() ufuvfvk () wV . Let be the vertex whose label wpq is the maximum value. Consider the star K1,n with vertex set 0i {, :1} xin and edge set 0 {:1}. i xin We superimpose the vertex x0 of the star K1,n graph on the vertex wV 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} VEpqpqpqnpq n vV()()defined by g(v) = f(v) for all and uvfuv for all .Euv From our construction of new graph , G 0 () () (). wgx gwpq ()2(1) , for 1. i xpqniin and (); for 1 i wxpq iin . Since th e graph G is super edge edgemagic with com mon count k1, implies that 1 () () () uguvgvk for Figure1. Edge bimagic total labeling of K1,6ôP5. Copyright © 2011 SciRes. AM
J. B. BABUJEE ET AL.1395 all Now we have to prove that the remaining edges joining w and .uv E:1 i 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 edgemagic total la beling then, admits edge bimagic total labeling. 1, Proof: Let G(p,q) be super edge edgemagic graph with the bijective function ôn GF :{1,2,, VE pq () such that 1 ()() ufuv () fvkwV . Let be the vertex whose label wpq 0 {, :1} i is the maximum value. Consider the Fan F1,n with vertex set 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 , VE pq 21,,31}qnpq n defined by 1, ,, ,pqn p () () pq vfv for all and vV() uv () uv for all .uv E From our construction of new graph G’, 0 () () (). wgx gwq p Now 15(1) 6 ()1,for 1 4 i ii xpq i n. and 1 ()33, for 11; ii gxxp qniin 1275( 1)6 ()1,for 1. 4 i ini wxp qin Since the graph G is super edge edgemagic with common count k1, implies that 1 () () () 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 edgemagic 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 edgemagic la beling and G2 has super vertex edgemagic labeling then, admits edge bimagic total labeling. 12 ôGG Proof: Let G1 be the super edge edgemagic then there exist the b ijecti ve function 11 11 :{1,2,,} VE pq () such that 1 ()() ufuvfvk ,uv V for all 1 , and Let G2 be the super vertex edgemagic then there exist the bijective function 22 22 :{ 1, 2,, } VE pq () such that 2 ()( ) uguvgvk ,.uv V, for all 2 Let 1 wV be the vertex whose label is the maximum value 11 pq and 12 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 x12 .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. Copyright © 2011 SciRes. AM
J. B. BABUJEE ET AL. Copyright © 2011 SciRes. AM 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 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 edgemagic total labeling then, G + K1 admits edge bimagic total labeling. Proof: Let G(p,q) be super edge edgemagic. Then there exist a bijective function function such that 1 :{1,2fV E (),, }pq()( ) 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 vpqi i p and () () uvfuv for all .uv E () 21 xpq and (); for 1. i xvpq iip Since the graph G is super edge edgemagic with common count k1, implies that 1 () () () 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 edgemagic labeling and G2 has super vertex edgemagic 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. 1246. [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. 451461. doi:10.4153/CMB19700841 [4] W. D. Wallis, “Magic Graphs,” Birkhauser, Basel, 2001. doi:10.1007/9781461201236 [5] J. B. Babujee, “Bimagic Labeling in Path Graphs,” The Mathematics Education, Vol. 38, No. 1, 2004, pp. 1216. [6] J. B. Babujee, “On Edge Bimagic Labeling,” Journal of Combinatorics Information & System Sciences, Vol. 28, No. 14, 2004, pp. 239244. [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. 107116. [8] J. B. Babujee and R. Jagadesh, “Super Edge Bimagicla beling for Graph with Cycles,” PacificAsian Journal of Mathematics, Vol. 2, No. 12, 2008, pp. 113122. [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. 171175. [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. 8592.
