### Journal Menu >>

 Open Journal of Discrete Mathematics, 2012, 2, 145-148 http://dx.doi.org/10.4236/ojdm.2012.24029 Published Online October 2012 (http://www.SciRP.org/journal/ojdm) Mean Cordial Labeling of Graphs Raja Ponraj1, Muthirulan Sivakumar2, Murugesan Sundaram1* 1Department of Mathematics, Sri Paramakalyani College, Alwarkurchi, India 2Department of Mathematics, Unnamalai Institute of Technology, Kovilpatti, India Email: ponrajmaths@indiatimes.com, sivamaths.vani_r@yahoo.com, sundaram_spkc@rediffmail.com Received August 12, 2012; revised September 4, 2012; accepted September 17, 2012 ABSTRACT Let f be a map from V(G) to. For each edge uv assign the label 0,1, 22fufv. f is called a mean cordial la- beling if  1ffviv j and  1ffeie j, ,0,1,2ij, where fvx and denote the number of vertices and edges respectively labelled with x (fex0,x1,2). A graph with a mean cordial labeling is called a mean cor- dial graph. We investigate mean cordial labeling behavior of Paths, Cycles, Stars, Complete graphs, Combs and some more standard graphs. Keywords: Path; Star; Complete Graph; Comb 1. Introduction The graphs considered here are finite, undirected and simple. The vertex set and edge set of a graph G are de- noted by V(G) and E(G) respectively. The cardinality of V(G) and E(G) are respectively called order and size of G Labelled graphs are used in radar, circuit design, com- munication network, astronomy, cryptography etc. [1]. The concept of cordial labeling was introduced by Cahit in the year 1987 in [2]. Let f: V(G) to{0,1} be a function. For each edge uv assign the label fufv. f is called a cordial labeling if 1ffviv j and  1,ffeie j where and denote the number of vertices and edges respec- tively labelled with x (x = 0, 1). A graph with admits a cordial labeling is called a cordial graph. Product cordial labeling was introduced by M. Sundaram, R. Ponraj and Somasundaram [3]. Here we introduce a new notion called mean cordial labeling. We investigate the mean cordial labeling behavior of some standard graphs. The symbol ,0,1ijfvxfexx stands for smallest integer greater than or equal to x. Terms not defined here are used in the sense of Harary [4]. 2. Mean Cordial Labeling Definition 2.1. Let f be a function from V(G) to {0,1,2}. For each edge uv of G, assign the label 2fufv. f is called a mean cordial labeling of G if 1ffviv j and 1,ffeie j ,0,1,2ij where fvx and fex denote the num- ber of vertices and edges labelled with x () re- spectively. A graph with a mean cordial labeling is called mean cordial graph. 0,1, 2xRemarks 2.2: If we restrict the range set of f to {0,1},the definition 2.1 coincides with that of product cordial labeling. Remarks 2.3: If we try to extend the range set of f to 0,1, ,2kk, the definition 2.1 shall not workout since 0fv becomes very small. Theorem 2.4: Every graph is a sub graph of a con- nected mean cordial graph. Proof: Let G be a given (p,q) graph. Take three copies of Kp. Let 123 respectively denote the first, se- cond and third copies of Kp. Let ,,GGG12,,vVGuVG wVG3. Let G* be the graph with 12VGVG VGVG3 and 123,EGEG EGEGuvvw . Clearly G* is a super graph of G. Assign the label 0 to all the vertices of G1,1 to all the vertices of G2, 2 to all the vertices of G3. Then and   012fffvvv pp02fpe, 112fe, 212fep .Therefore this labeling is a mean cordial labeling of G*. Theorem 2.5: Any Path is a mean cordial. nP*Associate professor (retired). Copyright © 2012 SciRes. OJDM R. PONRAJ ET AL. 146 Proof: Let be the Path . nPn12 nuu uCase (1): 0 mod 33.tLet Define n2,1ifuit, 1, 1tifuit0, 1 , 2tifuit. Then and  01ffvv 2fvt01,1 2fffetee .t1t1 Hence f is a mean cor- dial labeling. Case (2): 1 mod 3n31.Let Assign labels to the vertices i as in case (1). Then assign the label 0 to the vertex . Here. and f Hence f is a mean cordial labeling. nt1uin nu0,et   012fffvvv2.t1ffeeCase (3): 2 mod 3n32.Let Assign labels to the vertices i as in case (2). Then assign the label 1 to the vertex nu. Here nt1uin  011,2ff fvvtv ,t  f and e11.t02ffeet. Hence f is a mean cordial labeling. Illustration 2.6: Mean cordial labeling of is shown in Figure 1. 6PTheorem 2.7: The Star 1,nK is a mean cordial iff . 2nProof: Let and 1, ,:1niVKuui n:1 .ui n1,niEK u For , the result follows from Theorem 2.5. As- sume If possible let there be a mean cordial la- beling f. 2n2.nCase (1): 0.fu fu fv Then for all edge uv. This forces a contradiction. 20.2.fu2feCase (2): In this case again a contradiction. 0e0f,,Case (3): 1.fu0eHere also a contradiction. 0fHence 1,nK is not a mean cordial for all 2.nTheorem 2.8: The cycle is mean cordial iff . nCuu1,2 mod 3nCProof: Let be the cycle n0n12 1nuuCase (1):  mod 3tLet . Then . In this case a contradiction 3n0fen 012fffvvv od 3t1,t1 mCase (2): Let Define31.nt0,1 1ifuit 1,11tifui t2, 1 , 21tifuitt  Then 01fvt, 12ffvv and 2 1 2 2 2 1 100 0 1 01,tfv 12ffvv t and Figure 1. Mean cordial labeling of P6. Then 11etf, 02.ffeet Hence f is a mCase (3): ean cor- dial labeling.  mod 3 22nLet 3nt. Define 0,1 1ifuit, 1, 11tifuit, 2,1121tifuitThen  1fvt, 02ffvvt1 and 11etf, 02.eetff Hence f is a mean cor- he Complete graph dial labeling. Theorem 2.9: TnK is mean cor-dial iff 2.n Proof: Clearly 1K and 2K are mean cordial by Theorem 2.5. Assu2.n possible let there be a mean cordial labeling f. Case (1): me If 3 , 1.t0 modnLet 3nt Then  012fffvvvt  t02fe, t2212fett , and 222ftet . Then a con- tradiction. Case (2): 2102ffee t1, 1 mod 3n 1Let 3nt Subcase (i ) : 01fvt 12ffvvt 1t02fe,  112fetttt 1t and 222ftet , 212 2ffee tt1, a contra- diction. Subcase ( i i ) : 11fvt1t  02ffvvtt02fte,  2112fett and  212ftet t . 220ffeett1, a con- tradiction. Subcase (iii): 21fvtt t  01ffvv0,2fte 2112fettt and  1212ftet .t Then 102ffee tt21, a contradiction. Case (3): 2 mod 3n Let 32nt Subcase ( i) : 0fvt  12ffvv t111t02fte,  112fetttt and  21212ftet . Then Copyright © 2012 SciRes. OJDM R. PONRAJ ET AL. 147 21023ffee tt1vt1, a contradiction Subcase ( i i ) : f02ffvvtt11tt1,11tt1, 102fte, and 2112fett 1212ftet . Then  220ffeett2vt a contradiction. Subcase (iii): ft 01ffvvt1102fte2ftet and  2112fet21t2Then a contradic- tio 210 1ffeet ttn. Theorem 2.10: The Wheel is not a mean cordial grnWaph for all nProof: Let W where nC is the cycle 12 1nuu uu and 1VK If possible let there be a me labeling f. 3. 1nnCK.uan cordiale (1): Cas0 mod 3n Let Theze of the wheel is 3ntSubcase ( i) : n the si6.t0,futHere , a contradiction. 0 1fetSubcase ( i i ) : . 12t1or 2fuIn this case gain a contradiction. 0,et af1 mod 3nC ase (2): Let 31nffetet ac- cording as .nt The 021or 0 0,fu or 0,fu this is a contra- diction. Case (3): 2 mod 3nSimilarly to case (1e get a contradiction. ), wTheorem 2.11: 1, nSK is mean cordial, where S(G) debdivision of G.  (i): notes suProof: Let and 1, ,, :1niiVSKuuvin,:1iiiESKuuuvin1,n Case  0 mod 3n3.tLet nDefine 0,fu 0,1,ifuit 1,1 2tifuit0,1,i, fvit 2,12 ,tifvit, Then 021fvt122ffvvt and 01ffee2,t 22fet.oLet 1 He ean crdial lbeling. nce f is a me (2): aCas1 mod 3 1 Assign labels to the vertices ,iuu and 11ivin  as in case (1). Then assign the label 1 and 2 to the vertices and v respectively. Here n3tnnun and ,   0122fffvvv t02fet122ffee t1, Hence f is a mean cordial label-ing. Case (3): 2 mon32.ntd 3 Let vin Assign labels to the vertices and i (1,iuu1) as in case (2). Then assign the label 0 and 2 to the vertices, respectively. Here nunv022ffvv t2, and 12v1ft122fet, 2ffeet02 1, Hence f is a mean cordial labeling. Illustration 2.12: Mean cordial labeling of 1,6SK is shown in Figure 2. Theorem 2.13: The comb is mean cordial where 1nPK12GG denotes the corona of and . 1Proof: Let be the Path . Let Guu u2GnP12 n1nnVP KVP:1ivi n, :1iiuvi n1nnEP KEP Case (1): 0 mon3.nt d 3 Let  2, 1ifuit, 1, 1tifuit 20, 1tifuit, 2,1ifvit 1, 1tifvit, 20,1tifvit Then 2fv01ffvv 2t and 122,ffee t02fe t1, Hence f is a mean cordial labeling. Case (2): d 31 mon31nt Let iv1in . Assign labels to the vertices and (1iunu) as in case (1). Then assign the label 0 and 1 to the vertices and . Here nv1,22fv012ffvv t,t and 022,ffee t and 121fetHence f is a mean cordial labeling. Case (3): d 32 mon32.nt Let i (1in Assign labels to the vertices iu & v2) as in case (1). Then assign the label 0, 2 and 0, 1 to the vertices u and respec-tively. Here 1,nunn1,nvv02fvt2, and  122t1ffvv01fffeee221.t Hence f is a mean cor-dial labeling. Theorem 2.14: PnΘ2K1 is mean cordial. 0 1 11 1 111 1 0000000222222220 Figure 2. Mean cordial labeling of S(K1,6). Copyright © 2012 SciRes. OJDM R. PONRAJ ET AL. Copyright © 2012 SciRes. OJDM 148 Let 2, ,, :1niVKuvui n and Proof: Let Pn be the Path 12 Let vi and wi be the pendant vertices which are adjacent to .nuu u,1 .iuin 2, ,:1niiEKuuvuin . 2,1K and 2,2K are mean cordial by Theorem 2.5 and 2.8 respectively. Assume . Suppose f is a mean cordial labeling of 2,n2nK. Clearly either 0fu or Without loss generality we can assume so that fv00.fu0.fv Case (1): n is even. Define 0, 12infu i 21, 12ninfu i 0 mod 3nCase (1): 0, 12infv i 3.tn Then 0orfettLet 1, a contradiction since the size of 2,nK is 6.t1, 12infw i od 31 mnCase (2): ce Let n = 3t + 1. Here again a contradic-tion. 0ft,22, 12ninfv i Case (3): 2 mod 3n 0orfett2,nLet n = 3t + 2. Here 1, again a con- tradiction to the size of K. 22, 12ninfw i 3. Conclusion Then and   012fffvvv 01,12.eneennfff In this paper we introduced the concept of mean cordial labeling and studied the mean cordial labeling behavior of few standard graph. The authors are of the opinion that the study of mean cordial labeling behavior of graph ob- tained from standard graphs using the graph operation shall be quite interesting and also will lead to newer re-sults. Hence f is a mean cordial labeling. Case (2): n is odd. Define 10, 12infu i 1211, 12ninfu i  4. Acknowledgements 30, 12infvi  The authors are thankful to the referee for their valuable comments and suggestions. 31, 12infwi REFERENCES 11220nnfv fw     [1] J. A. Gallian, “A Dynamic Survey of Graph Labeling,” Electronic Journal of Combinatorics, Vol. 18, 2011, pp. 1-219. 11221, 2nnfv fw     [2] I. Cahit, “Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs,” Ars Combinatoria, Vol. 23, No. 3, 1987, pp. 201-207. 112212, 12nniinfv fwi [3] M. Sundaram, R. Ponraj and S. Somosundram, “Product Cordial Labeling of Graph,” Bulletin of Pure and Applied Sciences, Vol. 23, No. 1, 2004, pp. 155-162. Then and   012fffvvv 01,12.eneennfff [4] F. Harary, “Graph Theory,” Addision Wisely, New Delhi, 1969. Hence f is a mean cordial labeling. Theorem 2.15: The 2,nK is a mean cordial iff 2.n Proof: