### Journal Menu >>

 Applied Mathematics, 2011, 2, 1525-1530 doi:10.4236/am.2011.212216 Published Online December 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM On Signed Product Cordial Labeling Jayapal Baskar Babujee, Shobana Loganathan Department of Mat hematics, Anna University, Chennai, India E-mail: {baskarbabujee, shobana_2210}@yahoo.com Received September 19, 2011; revised October 25, 2011; accepted November 3, 2011 Abstract A new concept of labeling called the signed product cordial labeling is introduced and investigated for path graph, cycle graphs, star-K1,n, Bistar-Bn,n, and Some general results on signed product cordial labeling are studied. ,nPn3, 3.nCn Keywords: Graph, Labeling, Function, Cordial Labeling 1. Introduction If the vertices of the graph are assigned values subject to certain conditions then it is known as graph labeling. Most of the graph labeling problems have the following three common characteristics: a set of numbers for as- signment of vertex labels, a rule that assigns a label to each edge and some condition(s) that these labels must satisfy. Cordial labelings were introduced by Cahit [1] who called a graph G cordial if there is a vertex labeling such that the induced labeling , defined by :() 0,1fVG:() 0,1fEG*()() ()fxyf xfy, for all edges ()xyEG and with the following ine-qualities holding: (0)vv(1) 1ff and (0)(1) 1ffee, where (respectively ) is the number of vertices (respectively, edges) labeled with . Sundaram and Somasundaram [2] introduced the no-tion of product cordial labelings. A product cordial la-beling of a graph G with vertex set is a function ()fvi ()feiiVf from to  such that if each edge is as-signed the label V0,1() (uv)fufv, the number of vertices la-beled with 0 and the number of vertices labeled with 1 differ by at most 1, and the number of edges labeled with 0 and the number of edges labeled with 1 differ by at most 1. A graph with a product cordial labeling is called a product cordial graph. For detail survey on graph labeling one can refer Gal-lian [3]. Let be a graph. As given in [4] a mapping is called binary vertex labe- ling of G and (, )GVE:() 0,fVG()1fv) 0,1G is called the label of the vertex v of G under f. For an edge , the induced edge label- ing is given by e:(fE uv*()() ().fefufv Let be the number of vertices of G having labels 0 and 1 respectively under f and let be the number of edges having labels 0 and 1 respectively under (0),fv(1)fv.(0),fe(1)fef A binary vertex labeling of a graph G is called a cordial labeling if and (0) (ffee1) 1(0)vv(1) 1ff . In Section 2, we introduce the definition of signed product cordial labeling and work for few fundamental graphs. In Section 3 we prove that and bistar graph ,nn are signed product cordial. Finally in Sec-tion 4, we prove the existence of signed product cordial labeling for some general graphs. ,nnPCB 2. Signed Product Cordial Labeling We now introduce the definition of signed product cor-dial labeling. Definition 2. 1 : A vertex labeling of graph G with induced edge labeling defined by :() {fVG*:(){fEG1,1}1,1} () ()()fuvf uf v is called a signed product cordial labeling if (1)(1) 1ffvv and *(1f(1)fee )1, where (1)fv is the number of vertices labeled with –1, (1)fvis the number of vertices labeled with 1, (1)fe is the number of edges labeled with –1 and f is the num-ber of edges labeled with 1. A graph G is signed product cordial if it admits signed product cordial labeling. (1)eTheorem 2.2: The Path graph Pn, n ≥ 2 admits signed product cordial labeling. Proof: Let .., nv12,Vv,.v be the vertex set and 1in1;1iiEvv  be the edge set of the path graph J. B. BABUJEE ET AL. 1526 n. To define vertex labeling the following cases are to be considered. P:() {1,1}fVG4),2mod4, 3 mod4,2mod4, 3 mod4)1Case 1: when 0,1,3 (modnfor 1in1;1() 1; 0iifv i Case 2: when 2(mod 4)nfor 12in 1;1() 1; 0iifv i and 1()1,(nnfv fv The induced edge labeling f is given by *11()()()1() and(1() and(gniii iiiiifvv fvfvfv fvfv fv11)have samesign)havedifferentsi with respect to the above labeling pattern we give the proof as follows, i) When 0mod4nThe total number of vertices labeled with –1’s are given by (1) 2fvn and the total number of vertices labeled with 1’s are given by (1) 2f. Therefore the total difference between the vertices labeled with –1’s and 1’s is vn(1)(1) 0ff. The total number of edges labeled with –1’s are given by vv*(1)21enf and the total number of edges labeled with 1’s are given by *(1) 2enf. Therefore the total difference be-tween the edges labeled with –1’s and 1’s is **(1)(1)1 1ffee , differ by one. **(1)(1) 2(1) 1(1)2ffffvvnee  n ii) When 2mod 4nThe total number of vertices labeled with –1’s are given by (1) 2fvn and the total number of vertices labeled with 1’s are given by (1) 2fvn. Therefore the total difference between the vertices labeled with –1’s and 1’s is (1)(1) 0ffvv . The total number of edges labeled with –1’s are given by *(1) 2enf and the total number of edges labeled with 1’s are given by *(1)2 1f. Therefore the total difference between the edges labeled with –1’s and 1’s is en**(1)(1) 1ffee , differ by one. **(1)(1) 2(1)(1) 12ffffvvnee  n iii) When n is odd The total number of vertices labeled with –1’s are given by (1)1 2fvn  and the total number of vertices labeled with 1’s are given by (1)1 2fvn . Therefore the total difference between the vertices la-beled with –1’s and 1’s is (1)(1)1 1ffvv . The total number of edges labeled with –1’s are given by *(1)12fen  and the total number of edges labeled with 1’s are given by (1)12fen . Therefore the total difference between the edges labeled with –1’s and 1’s is **(1)(1) 0ffee, differ by zero. **(1) 1(1)1 2(1)(1)1 2ffffvvneen Thus in each cases we have (1)(1) 1ffvv  and **(1)(1) 1ffee. Hence the path graph Pn, n ≥ 2 ad- mits signed product cordial labeling. Theorem 2.3: The Cycle graph Cn, n ≥ 3 admits signed product cordial labeling except when . 2mod4nProof: Let 12,,,nVvv v be the vertex set and 11in vv1,1}1ii n be the edge set of the cycle graph Cn. To define vertex labeling the following case is to be consid-ered. ;1Evv:() {fVGWhen 0,1,3 (mod 4)n for 1in, 1; 1,2mod4() 1;0, 3 mod4iifv i The edge labeling is given by *1111()()()1() and()havesamesign1() and()have different signiii iiiiifvv fvfvfv fvfv fv In view of the above labeling pattern we have, Table 1. Table 1. Vertex and edge conditions of a cycle graph. n (1)fv (1)fv (1) (1)ffvv 0mod4n 2n 2n 0 1mod4n 12n 12n 1 3mod 4n 12n 12n 1 n *(1)fe *(1)fe **(1) (1)ffee 0mod4n 2n 2n 0 1mod4n 12n 12n 1 3mod4n 12n 12n 1 Copyright © 2011 SciRes. AM J. B. BABUJEE ET AL.1527 4Hence the cycle graph;2modnCnadmits signed product cordial labeling. Theorem 2.4: The star graphadmits signed product cordial labeling. 1, ,nKn2Proof: The star graph K1,n is a tree obtained by adding n pendent edge to the center vertex. Let be the vertex set and the edge set is given by . To define vertex labeling for is given by 12 1,,,,nnVvv vv1iEv:()fVG11in;2 1vin{1,1}for 1; 1mod2() 1;0 mod2iifv i When n is even and odd, the edge labeling is given by *12*12 1()1()1;1iifvv2fvvi n and *12*12 1()1;112()1;112iifvvi nfvvin 1 respectively. In view of the above labeling pattern we have, Table 2. Hence the star graph 1,nK admits signed product cor-dial labeling. 3. Signed Product Cordial Labeling for Special Graphs In this section we prove the signed product cordial la-beling for the graphs and the bistar graph . ,nnPC,nnTheorem 3.1: The Path graph admits signed product cordial labeling. B,nPn31Proof: Let 123 and 123 be the vertex sets of the path graph and the edge set is given by ,, nvvvv,, nuuu unP11 2;11 ,;1ii iiEvvinEvuin The graph n has 2n vertices and edges. To define vertex labeling the following P2n1,1}:() {fVG Table 2. Vertex and edge conditions of a star graph. n (1)fv (1)fv (1) (1)ffvv 0mod2n 12n 12n 1 1mod2n 12n 12n 0 n *(1)fe *(1)fe **(1) (1)ffee 0mod2n 2n 2n 0 1mod2n 12n 32n 1 cases are to be considered. Case 1: when n is even for 1in 1; 1,2mod4() 1;0, 3 mod4iifv i 1; 1mod2() 1;0m o d2iifu i The edge labeling are defined as follows for 11in 1111()()()1if() and() have samesign1 if()and()havedifferentsigniii iiiiifvvfvfvfv fvfv fv for 1in 11() ()()1if() and()havesame sign1if()and()havedifferentsigniii iiiiifvu fvfufv fvfv fv Case 2: When n is odd The vertex labeling is given by for 12in 1;1,2m o d4() 1;0, 3 mod4iifv i 1()1;()nnfvfv1 for 11in 1; 1mod2() 1;0m o d2() 1inifu ifu The edge labeling are defined as follows for 11in *1111()()()1if() and()havesamesign1 if()and()havedifferentsigniii iiiiifvv fvfvfv fvfvfv for 1in *11() ()()1if() and() have same sign1if()and()havedifferent signiii iiiiifvu fvfufv fvfv fv In view of the above labeling pattern we have, Table 3. Hence the graph admits signed product cordial labeling. ,nPn33Theorem 3.2: The graph admits signed product cordial labeling except for ,nCnn2mod 4.Copyright © 2011 SciRes. AM J. B. BABUJEE ET AL. 1528 Table 3. Vertex and edge conditions of the graph . , 3nPnn (1)fv (1)fv (1) (1)ffvv 0mod2n n n 0 1mod4n n n 0 3mod 4n n n 0 n *(1)fe *(1)fe **(1) (1)ffee 0mod2n n – 1 n 1 1mod4n n n – 1 1 3mod4n n – 1 n 1 Proof: Let 123 and 123 be the vertex sets of the graph n with 2n vertices and 2n edges. The edge set is given by ,, nvvvv,, nuuu u3,Cn11 12;1 1;1ii niiEvvinvvEvuinnn The vertex labeling is defined by for 1in1; 1,2mod4() 1; 0, 3 mod4iifv i 1; 1mod2() 1;0m o d2iifu i The edge labeling is given by for 1in*1111()()()1if() and()have same sign1 if()and()havedifferent signiii iiiiifvv fvfvfv fvfv fv 1*111if()and()havesame sign() 1if()and()havedifferent signiiniifv fvfvv fv fv 1*11()and()havesame sign() 1()and()havedifferent signiiii iifv fvfvu fv fv In view of the above labeling pattern we have, the total number of vertices labeled with –1’s are given by and the total number of vertices labeled with 1’s are given by . Therefore the total differ-ence between the vertices labeled with –1’s and 1’s is (1)fv(1)fv(1)(1) 0ff. The total number of edges labeled with –1’s are given by f and the total num-ber of edges labeled with 1’s are given by fvvnn(1)e(1)e. Therefore the total difference between the edges labeled with –1’s and 1’s is (1)(1) 0ffee, differ by zero. (1) (1)(1) (1)ffffvvee nn Hence the cycle graph admits signed prod-uct cordial labeling. ,nCn322Theorem 3.3: The graph admits signed product cordial lab e ling. ,,nnBnProof: The graph , is a bistar obtained from two disjoint copies of 1,n,nnBnK by joining the centre vertices by an edge. It has 2n + 2 vertices and 2n + 1 edges. Let 123 22,,,vvv ,nv be the vertices of the bistar graph. The edge set is defined as 1121222;1 ,;2 1iiEvvinEvv in  We now define vertex labeling as :() {1,1}fVG2211;1mod2;12() 1;0 mod2;322()1()1iniifv iifvfvnn11 The edge labeling is given by 2212 112 1()1;2()1()1;1inifvvi nfvvfvvi n  The total number of vertices labeled with –1’s are given by (1) 1fvn and the total number of vertices labeled with 1’s are given by . Therefore the total difference between the vertices labeled with –1’s and 1’s is (1)1fvn(1)(1) 0ffvv(1. The total number of edges labeled with –1’s are given by f and the total number of edges labeled with 1’s are given by )en(1) 1fen. Therefore the total difference between the edges labeled with –1’s and 1’s is (1)(1) 1ffee , differ by one. In view of the above labeling pattern we have, (1)(1) 11(1)(1) 11ffffvv nee n From the above labeling pattern we have (1)(1) 1ffvv and (1)(1) 1ffee . Hence the bistar graph , admits signed product cordial labeling. ,,nnBn2Example 3.4: Figure 1 illustrates the signed product cordial labeling for Bistar 5,5. Among the eleven edges five edges receive the label +1 and six edges receive the label –1. BCopyright © 2011 SciRes. AM J. B. BABUJEE ET AL.1529 Figure 1. Signed product cordial labeling of Bistar B5,5. 4. General Results on Signed Product Cordial Labeling In this section we prove the Signed product cordial la-beling for the some general graphs. Definition 4.1: The tree T@mK1 is obtained by at-taching m copies of K1 to any one of the vertices in T. Theorem 4.2: If a tree T admits signed product cor-dial labeling with n vertices then T@mK1 (m even) is also a signed product co rdial tree. Proof: Let us assume that a tree T admits signed prod-uct cordial labeling. The mapping satis-fies the condition of signed product cordial labeling. :{1,fV1})Let where and . The vertex labeling for , is defined as 1@(,TTmK VE12,,,nuu u ET()()VV12,,,nEvu vuvu :{1,1}gVgvfvvV,,,uu u. Let 12 m be the m vertices joined to the vertex v of the tree T. The vertex labeling of is given by ,,,mu12uu () (1);1iigui 12(),(), ,(m. If then the sign of ()fv 1,)mgvug vug vu), ,( )m will be the sign of 12(),(gugu gu12(),(), ,( respectively and if f(v) = –1 then the sign of )mgvug vug vu,(),,()m will be the sign of 12()gugu gu . In both the cases the new m edges 12,,,mvu vuvu contrib-utes equal number of edges labeled with –1’s and 1’s. Therefore in a tree T@mK1, the difference between the total number of vertices labeled with –1’s and 1’s and the difference between the total number of edges labeled with –1’s and 1’s differs by utmost one. Example 4.3: Figure 2 illustrates the signed product cordial labeling for T@4K1 where T is an arbitrary tree having signed product cordial labeling. Corollary 4.4: If a connected graph G has signed product cordial labeling then the graph G@mK1 where is even admits signed product cordial labeling. mDefinition 4.5: The tree is obtained by super-imposing a pendant vertex of with any of the se-lected vertex in T. ˆ0nTPnPTheorem 4.6: If a tree T as signed product cordial labeling then where m is od d admits signed p rod-uct cordial labeling. ˆ0nTP Figure 2. Signed product cordial labeling of T@4K1. Proof: Let (,)TVE be a connected graph with vertex set V and edge set E then the tree ˆ0(,nTP VE) where ,nVV u12,,uu  and 1iiu1;1u inEE. Let be a vertex in T. we superimpose a pendant vertex with a selected vertex v in T only if they preserves the same sign. vCase 1: If 1()( )1fv fu, then the vertex labeling for the path graph follows from theorem 2.2Case 2: If 1()( )1fv fu , then the vertex labeling is given by Sub Case 2.1: when 0,1,3(mod 4)n for 1in () 1;0,3mod41;1,2m o d4ifv ii  Sub Case 2.2: when 2(mod4)n for 12in () 1;0,3mod41;1, 2 mod4ifv ii  and 1()1,()nnfv fv1 As we superimpose the pendant vertex of n with any one of the vertex in T provided they preserve the same sign then the path graph contributes equal number of vertices and edges labeled with –1’s and 1’s. Hence the tree admits signed product cordial labeling. Pˆ0nTPCorollary 4.7: If a connected graph G has signed product cordial labeling then the graph where n is odd admits signed product cordial labeling. ˆ0nTPTheorem 4.8: If a connected graph G has a signed product cordial labeling with n vertices (0mod4n) then G+ admits signed product cordial. Proof: Let (, )GVE be a connected graph with vertex set ,nu12,,Vuu. Since G has a signed product cordial labeling there exists such :{1,1fV }that (1)(1) 1ffvv and (1)(1) 1.ffee  Copyright © 2011 SciRes. AM J. B. BABUJEE ET AL. Copyright © 2011 SciRes. AM 1530 As 0mod4,n(1)(1) 0.ffvv Let where and 2. For our convenience let us as-sume that f maps all the vertices of to 1 and all the vertices of 2V to –1. The graph is ob-tained by attaching the pendant vertices to each of the vertices in G. Let the ver-tex set and edge set of be defined as and 12V:0modiVui,:1iiVuu iVV1:1mod2iVui1VGV12,,,nuu uGn;1iiEEuu2,E12,,uuithis labeling pattern the graph admits signed prod-uct labeling where n is a multiple of . G4 ,nunG:gV{1,. 5. Acknowledgements The referee is gratefully acknowledged for their sugges-tions that improved the manuscript. The vertex labeling for the graph , is defined as follows for, 1}1in6. References [1] I. Cahit, “Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs,” Ars Combinatoria, Vol. 23, 1987, pp. 201-207. () ()iigufu ()1when0mod2and() 1if0mod41when1mod2and()1if1mod41when0mod2and( )1if2mod41when1mod2and( )1if3mod4iiiiiguifuiifuiifuiifui   [2] M. Sundaram, R. Ponraj and S. Somasundram, “Total Product Cordial Labeling of Graphs,” Bulletin of Pure and Applied Sciences: Section E. Mathematics and Statis-tics, Vol. 25, 2006, pp. 199-203. [3] J. A. Gallian, “A Dynamic Survey of Graph Labeling,” Electronic Journal of Combinatorics, Vol. 17, No. DS6, 2010, pp. 1-246. [4] S. K. Vaidya, N. A. Dani, K. K. Kanani and P. L. Vihol, “Cordial and 3-Equitable Labeling for Some Star Related Graphs,” International Mathematical Forum, Vol. 4, No. 31, 2009, pp. 1543-1553. The induced edge labels () ().guvf uvuvE()ii All the newly added edges guu will share equally the labels –1 and 1 as per our construction above. Hence (1)(1) 0ggvv  and (1)(1) 0.ggee Only by