 Applied Mathematics, 2011, 2, 1270-1278 doi:10.4236/am.2011.210177 Published Online October 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM Further Results on Pair Sum Labeling of Trees Raja Ponraj1, Jeyaraj Vijaya Xavier Parthipan2 1Department of Mat hem at i cs, Sri Paramakalyani College, Alwarkurichi, Indi a 2Department of Mat hem at i cs, St.John’s College, Palayamcottai, India E-mail: ponrajmath@gma il.com, parthi68@rediffmail.com Received August 4, 2011; revised September 3, 2011; accepted Septe mber 10, 2011 Abstract Let G be a ,pq graph. An injective map :1,2,,fVG p  is called a pair sum labeling if the induced edge function,  :efEG Z0 defined by efuvf ufv is one-one and efEG is either of the form12 2,,,qkk k  or 12 12 12,,,qqkk kk  according as q is even or odd. A graph with a pair sum labeling is called a pair sum graph. In this paper we investigate the pair sum label-ing behavior of some trees which are derived from stars and bistars. Finally, we show that all trees of order nine are pair sum graphs. Keywords: Path, Star, Bistar, Tree 1. Introduction Notation 2.1: We denote the vertex and edge sets of star 1,nK as follows: The graphs in this paper are finite, undirected and simple. and will denote the vertex set and edge set of a graph G. The cardinality of the vertex set of a graph G is called the order of G and is denoted by p. The cardinality of its edge set is called the size of G and is denoted by q. The concept of pair sum labeling has been introduced in.The Pair sum labeling behavior of some standard graphs like complete graph, cycle, path, bistar, and some more standard graphs are investigated in [1-3]. Terms not defined here are used in the sense of Harary . All the trees of order ≤8 are pair sum have been proved in . Here we proved that all trees of order nine are pair sum. Let x be any real number. Then VGEGx stands for the largest integer less than or equal to x and x stands for the smallest inter greater than or equal to x. 1, ,:1niVKuui n and 1, 1niEKuui n . 2. Pair Sum Labeling Notation 2.2: We denote the vertex and edge sets of bistar as follows: ,mnB,,, ,:1,1mni iVBuvuvim in and ,,, :1,1mni jEBuvuuvvimj n. Theorem 2.3 : All graphs of order ≤8 are pair sum. Now we derive some pair sum trees which are used for the final section. 3. Pair Sum Labeling of Star Related Graphs Definition 2.1: Let G be a ,pq2,, graph. An injective map  :1,fVG  p is called a pair sum labeling if the induced edge function, :efEG Z0 defined by is one-one and efEGq is either of the form or 12 /2,,,qkk k ,,..., qkk kk Here we prove that some trees which are obtained from stars are pair sum. Theorem 3.1: The trees with vertex set and edge set given below are pair sum. ,(1 5)iGi12 (1)/2(1)/2 according as q is even or odd. A graph with a pair sum labeling defined on it is called a pair sum graph. 1) 11,:1 6niVG VKvi and R. PONRAJ ET AL. 1271...3,3.711,112 2334 4556,,,,,nEGEKuvvvvv vvvv vv Then is a pair sum graph. 1G2) 21,:1 7niVG VKviand 21,667 1223 34455,,,,,,nEGEKuv vvvv vvvvvvvu Then is a pair sum graph. 2G3) 31,:1 7niVG VKviand 31,556 6712 2334 4,,,,,,nEGEKuvvvvv vv vv vv vu Then is a pair sum graph. 3G4) 41, :1 4niiVG VKvwiand 41,112334122344,,,,,,.nEGEKuww wuwwwv vvvvv vu Then is a pair sum graph. 4G5) 51,,:1 3niiVG VKvwi and 51,12311223,,, ,,nEGEKuvuvuvv wvwvw Then is a pair sum graph. 5Proof 1): Define G 1:1,2,,fVGn  by   1234561,7,5, 1,3, 5,724,1 2ifu fvfvfvfv fv fvfuii n   and (1)/2 26,1 2nifuii n . Then is a pair sum tree. □ 1Proof 2): Define a map G 2:1,2,,fVGn 8 by and (/2) 28,1 22niifuiin. Then is a pair sum graph. □ 2Proof 3): Define a map G3:1,2,,fVGn8 by   12345671(/2)3,6, 1,4, 2, 3,4,1,7 ,12,10,12nifv fvfvfvfvfv fvfu fuiin fuiin    . Then is a pair sum graph. □ 3Proof 4): Define a map G4:1,2,,fVGn 9 by  12 3412341, 3,2, 1,4,5,6, 7,4.fufv fvfv fvfwfwfw fw   For the other vertices we define, (1)/252,1 272,1 2.inifuiinfuii n   Obviously f is a pair sum labeling. □ Proof 5): Define 5:1,2,,fVGn7 by  123123(1)1, 2,3,4,3,5, 7,24,1 222,12.inifufvfvfvfw fwfwfuii nfuiin     Obviously f is a pair sum labeling. □ Illustration 1: A pair sum labeling of the tree with 1G10n is 75 3 1 –5 –7 –1 12 84 –4 –12 –8 –6 –8 –10 –1481012 14 16 –7 –9 –11 –13 –15 7 9 15 13 11 –12    1234567113,6, 1,4, 1,3,4,2, 7,42,1 2ifv fvfvfvfv fvfvfu fufuiin     Copyright © 2011 SciRes. AM 1272 R. PONRAJ ET AL. Illustration 2: A pair sum labeling of the tree with is 3G9n –6 –3 –1 –4 1 2 3 4–9 –7 –5 –3 3 5 7 8 9 10 11 12 –11 –12 –13 –14 9 10 11 12 13 –10 –11 –12 –13 Illustration 3: A pair sum labeling of the tree with is 5G11n 10 8 6 12 14 16 –4 –6 –8 –10 –12 4 –3 –7–5–2 3 2 –3–1 2 1 5 7 9 11 13 15 –5 –7 –9 –11 –13 3 –1 4. Bistar Related Graphs In this section we show that some trees which are ob-tained from bistar are pair sum. Theorem 4.1: Let G be the tree with ,:1 6mn iVG VBwi and ,112234455,,,,,mnEGEBvwwwwwvw wwww 6.8 Then G is a pair sum graph. Proof: Define  :1,2,,fVGmn  and    1234564, 5, 6,2,7,4, 2,1.fw fwfwfwfwfwfu fv  Case 1): mnCase 2): mnAssign the label to as in case 1). De-fine ,1iiuvin8,1nifun iim n 2 and 213, 12mn ifun iim n  Case 3): mn Assign the label to ,1iiuvim as in case 1). De-fine 11,12mifvm iinm  210, 12.mn ifvmiinm  Then G is a pair sum graph. □ Theorem 4.2: If G is the tree with ,:13mn iVG VBwi and ,112233,,,mnEGEBuww wwwwvuv . Then G is a pair sum tree. Proof: Define a function :1,2,,fVGmn 5 by  1231, 3,4,1,2.fufv fwfwfw  Case 1): mn. 5,1ifuiin and 3,1i.fviin Case 2): . mnAssign the label to as in case 1). De-fine ,1iiuvin5,1nifuniim n 2 27,12mn ifun iim n. Then G is a pair sum graph □ 113,9, 11,10, 1.iifufuii nfvii n   Illustration 4: A pair sum labeling of the tree in theo-rem 4.2 with 10m, 6n is given below: Copyright © 2011 SciRes. AM R. PONRAJ ET AL. Copyright © 2011 SciRes. AM 1273 –4 –3 1 3 2 5 3 4 5 6 7 8 9 7 8 9 10 11 12 –9 –8 –1 –5 –7 –6 15 14 –13 –12 –11 –10 –10 –9 –8 –7 14 13 –14 –13 –12 –11 Theorem 4.3: Let G be the tree with and edge set ,:1 4mn iVG VBwi ,11223445,, ,, ,mnEGEBuwwv vww wvwwwuv . Then G is a pair sum tree. and ,1122334,,,,mnEGEBuwwwwvvwwwuv Proof: Define . :1,2,,fVGmn 7 Then G is a pair sum graph. by Proof: Define :()1,2, ,6fVG mn   1234 51, 1,4,2,3,3, 5.fufv fwfwfw fwfw  by Case 1): mn  12341, 2,4,1,3, 4.fufv fwfwfw fw  5,1ifuiin and Case 1): . mn5,1ifviin 116,6, 11ifufu iin  Case 2): mnand Label the vertices and as in case 1) for iuiv1in5,1.ifvii n . Define 5,1nifuniim n 2 Case 2): . mnAssign the label to ,1iiuvin as in case 1). De-fine and 26,1 2mn ifun iim n . 5,1nifuniimn 2 Case 3): mn and Assign the label to ,1iiuvin as in case 1). De-fine 28,1 2mn ifun iim n . 5,1mifvm iinm2 Case 3): . mnAssign the label to ,1iiuvin as in case 1). De-fine and 27,1 2mn ifvmiin m . 8,1mifvm iin m2 and Then G is a pair sum graph. □ Theorem 4.5: Let G be the tree with 2()5,1mn ifvm iinm 2. ,:15mn iVG VBwi Then G is a pair sum graph. □ Theorem 4.4: The tree G with vertex set and ,:15mn iVG Bwi ,12233445,,,,,. mnEGEBww wuuwwvvw wwuv R. PONRAJ ET AL. 1274 7.Then G is a pair sum tree. Proof: Define a function :1,2,,fVGmn  by  1234 54, 2,6,1,1, 3, 4.fufv fwfwfw fwfw  Case 1): mn6,1ifuii n. and 8,1ifvii n. Case 2): mnAssign the label to as in case 1). De-fine ,1iiuvim8,1mifvmiin m2 and 212, 12.nm ifvmiin m  Then G is a pair sum graph. Illustration 5: A pair sum labeling of the tree in theo-rem 4.5 with , is given below: 6m11n –6 –7 –1 –5 –4 –3 1 3 2 5 3 7 4 9 10 11 12 13 14 15 16 17 –20 –21 11 12 13 14 15 16 17 18 19 –18 –19 –10 –9 –8 –7 –13 –12 –11 –17 –16 –15 –14 –13 –12 –11 Theorem 4.6: Let G be the tree with ,:1 4mn iVG VBwi and ,1 122334,, ,,mnEGEBuwwvvwww wwuv .6. Then G is a pair sum tree. Proof: Define a function  :1,2,,fVGmn  by  12341, 1,4,2,3, 4.fufv fwfwfw fw  Case 1): mn6,1ifuiin and 6,1i.fviin Case 2): .mn Assign the label to ,1iiuvim as in case 1). De-fine 7,1mifvmiin m2 and 26,1 2mn ifvm iimn . Case 3): . mnAssign the label to as in case 1). De-fine ,1iiuvin5,1nifuniim n 2 and 28,1 2mn ifun iim n . Then G is a pair sum graph. □ Theorem 4.7: Let G be the tree with ,:1 4mn iVG VBwi and ,112233,,,mnEGEBvwww wwww 4. Then G is a pair sum tree. Proof: Define a function :1,2,,fVGmn 6 by 12341, 2,3,1,2, 3.fu fvfwfwfw fw . Case 1): mn 6,1ifuiim and 13,1 1.ifvii m Case 2): .mn Assign the label to ,1iiuvim as in case 1). De-fine 2,1mifvmiin m2 and 27,1 2mn ifumiin m . Case 3): . mnCopyright © 2011 SciRes. AM R. PONRAJ ET AL. 1275Assign the label to ,1iiuvin as in case 1). De-fine 6,1nifuniim n2 and 25,1 2mn ifun iim n . Then G is a pair sum graph. □ Theorem 4.8: The tree G with ,:15mn iVG VBwi and ,1122344,,,,mnEGEBvwww wwvw ww 5.7 Then G is a pair sum graph. Proof: Define a map  :1,2,,fVGmn  by  123451, 2,3,4,1,5, 4.fu fvfwfwfw fwfw  Case 1): .mn7,1ifuii m and 4,1i.fvii m. Case 2): mnAssign the label to as in case 1). De-fine ,1iiuvim4,1mifvmiin m2 and 28,12mn ifum iin m .. Case 3): mnAssign the label to ,1iiuvin as in case 1). De-fine 7,1nifun iim n2 and 25,1 2mn ifun iim n . Then G is a pair sum graph. □ Theorem 4.9: The tree G with ,:15mn iVG VBwi and ,122 33445,,, ,mnEGEBww wuvwww ww . Then G is a pair sum graph. Proof: Define a map :1,2,,fVGmn 7 by  123454, 1,6,1,2, 3, 4.fufv fwfwfw fw fw  Case 1): .mn 1115,6,11,8ifufuii mfv and 19,1 1ifuii m. Case 2): .mn Assign the label to ,1iiuvim as in case 1). De-fine 8,1mifvmiin m2 and 210, 12.mn ifumiin m  Case 3): .mnAssign the label to as in case 1). De-fine ,1iiuvin5,1nifuniim n 2 and 213, 12.mn ifun iim n  Then G is a pair sum graph. □ Theorem 4.10: The tree G with ,:16mn iVG VBwi and ,12233455,,, ,,mnEGEBwwwuvwww vw ww 6. Then G is a pair sum graph. Proof: Define a map :1,2,,fVG mn 8 by   1234564, 1,6,1,2, 3,3, 5.fufv fwfwfwfw fwfw  Case 1): .mn 4,1 ,6iifuii mfv and Copyright © 2011 SciRes. AM R. PONRAJ ET AL. Copyright © 2011 SciRes. AM 1276 .17,1 1.ifvii m  Case 2): mnAssign the label to as in case 1). De-fine ,1iiuvim6,1mifvmiin m 2 and 28,12mn ifum iin m .. Assign the label to as in case 1). De-fine ,1iiuvin11, 12nifuniimn and 24,1 2mn ifuniim n . Then G is a pair sum graph. □ Illustration 6: A pair sum labeling of the tree in theo-rem 4.10 with 10m, 5n is given below Case 3): mn –6 –7 –1 –2 –3 2 5 3 2 5 311 10 9 810 11 12 –5 13 –4 –3 1 6 7 9 –9 –8 –7 –6 –5 –13 –12 –11 –10 –9 –15 –14 15 14 –11 –10 1918 17 Theorem 4.11: The tree G with and 25,12mn ifum iin m ,:1 4mn iVG VBwi . ,122 3344,,, ,mnE GEBwwwuuwwwwvuv .6 Case 3): . mnAssign the label to as in case 1). De-fine ,1iiuvinThen G is a pair sum graph. Proof: Define a map 4,1nifuniim n2  :1,2,,fVGmn  and by 26,1 2mn ifuniim n  12341,1,3,2,4, 2.fu fvfwfwfw fw   . Then G is a pair sum graph. □ Theorem 4.12: The tree G with Case 1): .mn,:13mn iVG VBwi 4,1ifuii m. and ,112232,,,mnEGEBuwwwww wvuv . 5,1ifvii m. Then G is a pair sum graph. Case 2): mnProof: Define a map Assign the label to as in case 1). De-fine ,1iiuvim:1,2,,fVGmn 5 6,1mifvmiin m 2 by R. PONRAJ ET AL. 1277 1231, 1,2,3,5.fufv fwfwfw  Case 1): .mn3,1ifuii m and 3,1.ifvii m. Case 2): mnAssign the label to as in case 1). De-fine ,1iiuvim3,1mifvmiinm2 and 25,12mn ifum iin m .. Case 3): mnAssign the label to ,1iiuvin as in case 1). De-fine 3,1nifun iim n2 and 25,1 2mn ifun iim n . Then G is a pair sum graph. □ Theorem 4.13: The tree G with ,:13mn iVG VBwi and ,112231,,,mnEGEBuwww wwwvuv .5 Then G is a pair sum graph. Proof: Define a map :1,2,,fVGmn  by  1231, 3,2,3,2.fufvfwfwfw  Case 1): .mn5,1 ,ifuii m 3,1.ifvii m. Case 2): mnAssign the label to as in case 1). De-fine ,1iiuvim3,1mifvmiin m2 and 29,12mn ifumiin m . Case 3): . mnAssign the label to as in case 1). De-fine ,1iiuvin5,1nifuniim n 2 and 27,12mn ifun iim n. Then G is a pair sum graph. □ Theorem 4.14: The tree G with ,:13mn iVG VBwi and ,212232,,,mnEGEBuwww wwwvuv . Then G is a pair sum graph. Proof: Define a map :1,2,,fVGmn 5 by  1231, 3,5,2,1.fu fv fwfwfw  Case 1): .mn 42,1ifuiim and 2,1 .ifviim Case 2): . mnAssign the label to as in case 1). De-fine ,1iiuvin32 ,12nifuniim n and 252 ,12.mn ifun iim n  Then G is a pair sum graph. □ Illustration 7: A pair sum labeling of the tree in theo-rem 4.14 with 9m, 6n is given below: Copyright © 2011 SciRes. AM R. PONRAJ ET AL. Copyright © 2011 SciRes. AM 1278 –5 –3 2 3 1 –1 1 –1 –2 –4 –6 –8 –10 –12 –11 –13 –15 –9 –7 –5 –3 12 10 8 6 11 9 7 5 13 15 –17 –18 17 18 –17 –16 16 14 5. Trees of Order 9 Here we prove that all trees of order ≤9 are pair sum. Theorem 5.1: The trees given below are pair sum. 1) 2) 3) 4) 5) 6) 7) 8) 9) , 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) Proof: Graphs in case 1) to case 5) are pair sum by theorem 3.1. and case 6) to case 19) graphs are pair sum by theorem 4.1 to 4.14. □ Remark 5.2: The remaining trees of order 9 are pair sum by theorems in . Theorem 5.3: All trees of order 9 are pair sum. Proof: Follow from theorem 5.1 and Remark 5.2. Theorem 5.4: All trees of order ≤9 are pair sum. Proof: Follow from theorems 2.3, 5.3. □ 6. Acknowledgements The authors thank the referees for their comments and valuable suggestions. 7. References  R. Ponraj and J. V. X. Parthipan, “Pair Sum Labeling of Graphs,” The Journal of Indian Academy of Mathematics, Vol. 32, No. 2, 2010, pp. 587-595.  R. Ponraj, J. V. X. Parthipan and R. Kala, “Some Results on Pair Sum Labeling,” International Journal of Mathe-matical Combinatorics, Vol. 4, 2010, pp. 53-61.  R. Ponraj, J. V. X. Parthipan and R. Kala, “A Note on Pair Sum Graphs,” Journal of Scientific Research, Vol. 3, No. 2, 2011, pp. 321-329. doi:10.3329/jsr.v3i2.6290  F. Harary, “Graph Theory,” Narosa Publishing House, New Delhi, 1998.  R. Ponraj, J. V. X. Parthipan and R. Kala, “Pair Sum Labeling of Some Trees,” The Journal of Indian Academy of Mathematics (Communicated), in Press.