 Applied Mathematics, 2011, 2, 1393-1396 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 E-mail: 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 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 . All graphs considered here are finite, simple and undirected. We follow the notation and terminology of . 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,,() () ().fufuvfvk(( 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,, }fVG p. Wallis  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  and studied in  as (1,1) ed ge 1k2.kbimagic labeling. A graph with p vertices and q edges is called total edge bimagic if there exists a bi-jection (,)Gpq1,2,,:{ }.fVE,uv Epq such that for any edge  we have two constants 1 and 2 with 12k k()()() or .fufvfuvk k A total edge-bimagic graph is called super edge-bimagic if (()), ,}{1,2fVG p. Super edge-bimagic labeling for path, star-1,1, ,nnn are proved in . Super edge-bimagic labeling for cycles, Wheel graph, Fan graph, Gear graph, Maximal Planar class-Pln: ,KK5,n1, 1, 11,(, 1),( 2),,mnnn mnKKmn PPnPK31,22 12( 1),(3),)(nnCKnPNnPmKN 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,,}fVE pq  such that J. B. BABUJEE ET AL. 1394 for any edge uv in E we have a constant k with () () ().fufuvfvk A total edge-magic graph is called super edge edge-magic if (()) {1,2,,}.fEG q1)q(,)Gpq22ô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(,Gp2ôGGGq1.G1ppônGP12 12Theorems 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 }fVE pq 1. such that()()()fufuvfv kwV. Let be the vertex whose label ()fwpq is the maximum value. Consider the path Pn with vertex set {:1 }ixinwVônGGP{:2 }iVV xin {, :2iiEEwxxx 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}.iixxi n 1}.{1,2,,, 1,p qpq () ()21 Consider the bijec- tive function defined by in:'E2},gvfv for all and vV()()guv() (f uv.uv EG() . for all From our construction of new graph , 1)fwgx gwpq 2 , even 22For 2, () iingx2()gwx1( )iigxxp q1,k() () ()1 , odd2 nipq iipq i Now 2(1p qn ); 21 for 21.n iin  Since the graph G is super edge edge-magic with common count implies that 1guguvgvk{, :21iiwxx xin for all Now we have to prove that the remaining edges in the set have the common count k2. .uv E21For the edge wx2, }222() () 22332gw gwxpqpqpq( )+ 222gxnn pqnn k   For any edge xixi+1, if i is even, 112() () ()22122332 22iiiigx gxxgxni ipqpq nipqnpqn k2  If i is odd, 112() () ()11+21 22=33222iiiigx gxxgxinpqpqnipqnpqn k2i    Thus ônGGP has two common count k1 and k2. Hence has edge bimagic total labeling. ônGPExample 2.4 Taking 1,6 which is super edge edge magic, by using the theorem 2.3, 51,65GKôô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. ônGKProof: Let G(p,q) be super edge edge-magic graph with the bijective function :{1,2,,}fVE pq 1() such that ()()fufuvfvk() wV . Let be the vertex whose label fwpq is the maximum value. Consider the star K1,n with vertex set 0i{, :1}xxin and edge set 0{:1}.ixxin 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,ôGGKn with vertex set and {:1 }iVV xin {:1 }.iwx inEE:{1,2,, Consider the bijective function , 1,,,,2}gVEpqpqpqnpq n vV()()defined by g(v) = f(v) for all and guvfuv for all .Euv From our construction of new graph , G0() () ().fwgx gwpq ()2(1) , for 1.igxpqniin and (); for 1igwxpq iin . Since th e graph G is super edge edge-magic with com- mon count k1, implies that 1() () ()guguvgvk 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:1ixin have the common count k2. For any edge wxi, 2() () ()2(13321.iigw gwxgxpqpqipqnipqn k )} Thus we have 1, has two common count k1 and k2. Hence has edge bimagic total labeling. ônGGKônGK1, 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 ônGF:{1,2,,fVE pq () such that 1()()fufuv() fvkwV . Let be the vertex whose label fwpq0{, :1}i is the maximum value. Consider the Fan F1,n with vertex set xxin}{: 11}.iiixx in {:1 }iVV 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nFw1,ôGG 1{ :11}.iiixx in:'{1,2,, and Consi- der the bijective function {:1 }wx in EE ,gVE pq  21,,31}qnpq n  defined by 1, ,, ,pqn p() ()pqgvfv for all and vV()guv ()fuv for all .uv EFrom our construction of new graph G’, 0() () ().fwgx gwq p Now 15(1) 6()1,for 14iiigxpq i  n. and 1()33, for 11;iigxxp qniin 1275( 1)6()1,for 1.4iinigwxp qin   Since the graph G is super edge edge-magic with common count k1, implies that 1() () ()guguvgvk1}{ :11iiinx 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()()() 11275( 1)615( 1)6144= 3().iiiigwgwxgxp qp qnipqpqn k   i And for the edge xixi+1, 111215(1) 6() () ()1415(1)6( 1)33 143() .iiiiiiigxgxxgxp qipqnipqpqn k    Thus we have 1,ônGGF has two common count k1 and k2. Hence has edge bimagic total labeling. 1,nExample 2.7 illustrates the labeling technique used in the above theorem 2.6. ôGFExample 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ôGGProof: Let G1 be the super edge edge-magic then there exist the b ijecti ve function 11 11:{1,2,,}fVE pq () such that 1()()fufuvfvk ,uv V for all 1, and Let G2 be the super vertex edge-magic then there exist the bijective function 22 22:{ 1, 2,, }gVE pq () such that 2()( )guguvgvk ,.uv V, for all 2Let 1wV be the vertex whose label is the maximum value 11pq and 12xV be the vertex with label 1. We su- perimpose the vertex x1 of G2 graph on the vertex 1wV. Now we define the new graph called with vertex set 12ôGGG1x12.EEE:{1,2,, 1hV Ep q 1122 }pqpq12VV and Con- sider the bijective function 11 V11, 1,,pq ,11pq  defined by 1()() for all ();hufuuVGw 1() () for all ();h uvfuvuvEG 11() ();hwhxpq1 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 1Since 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 11111123()( )()1()()1 ()3( 1).hu huv hvpqgu pqguvpqg vpqk k  So has two common count k1 and k3. Hence admits edge bimagic total labeling. 12ôGGGôGG12Theorem 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()( )fufuvGGfvk1K. 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}{:iEE xv,, , p qp q{1,2Since there are p vertices in the graph G, ()1 for 1igvpqi i p and () ()guvfuv for all .uv E() 21gxpq and (); for 1.igxvpq iip Since the graph G is super edge edge-magic with common count k1, implies that 1() () ()guguvgvk. Now we have to prove that the remaining p edges joining V and x have the common count k2. For any edge xvi, 2()()( )21432 .iigx gxvgvpq pqipqipqk1 Thus we have 1 has two common count k1 and k2. Hence has edge bimagic total labeling. GGK1K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  J. A. Gallian, “A Dynamic Survey of Graph Labeling,” Electronic Journal of Combinatorics, Vol. 17, No. 1, 2010, pp. 1-246.  N. Hartsfield and G. Ringel, “Pearls in Graph Theory,” Academic Press, Cambridge, 1990.  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  W. D. Wallis, “Magic Graphs,” Birkhauser, Basel, 2001. doi:10.1007/978-1-4612-0123-6  J. B. Babujee, “Bimagic Labeling in Path Graphs,” The Mathematics Education, Vol. 38, No. 1, 2004, pp. 12-16.  J. B. Babujee, “On Edge Bimagic Labeling,” Journal of Combinatorics Information & System Sciences, Vol. 28, No. 1-4, 2004, pp. 239-244.  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.  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.  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.  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.