### Paper Menu >>

### 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. , n Pn 3, 3. n Cn 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 *()() () f xyf xfy, for all edges () x yEG and with the following ine- qualities holding: (0)vv(1) 1 ff and (0)(1) 1 ff ee, 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 () f vi () f ei i V f from to such that if each edge is as- signed the label V 0,1 () ( uv ) f ufv, 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 () 1 f v ) 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 u v *()() (). f efufv 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), f v(1) f v . (0), f e(1) f e f A binary vertex labeling of a graph G is called a cordial labeling if and (0) ( ff ee1) 1(0)vv(1) 1 ff . 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. , nn PC 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} () ()() f uv f uf v is called a signed product cordial labeling if (1)(1) 1 ff vv and *(1 f (1) f ee )1, where (1) f v is the number of vertices labeled with –1, (1) f v is the number of vertices labeled with 1, (1) f e 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)e Theorem 2.2: The Path graph Pn, n ≥ 2 admits signed product cordial labeling. Proof: Let .., n v 12 ,Vv,.v be the vertex set and 1in 1;1 ii Evv 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; 0 i i fv i Case 2: when 2(mod 4)n for 12in 1;1 () 1; 0 i i fv i and 1 ()1,( nn fv fv The induced edge labeling f is given by * 11 ()()() 1() and( 1() and(gn iii i ii ii fvv fvfv fv fv fv fv 1 1 )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) 2 f vn and the total number of vertices labeled with 1’s are given by (1) 2 f. 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 1 ff ee , differ by one. ** (1)(1) 2 (1) 1(1)2 ff ff vvn ee n ii) When 2mod 4n The total number of vertices labeled with –1’s are given by (1) 2 f vn and the total number of vertices labeled with 1’s are given by (1) 2 f vn. Therefore the total difference between the vertices labeled with –1’s and 1’s is (1)(1) 0 ff vv . 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 1 f. Therefore the total difference between the edges labeled with –1’s and 1’s is en ** (1)(1) 1 ff ee , differ by one. ** (1)(1) 2 (1)(1) 12 ff ff vvn ee n iii) When n is odd The total number of vertices labeled with –1’s are given by (1)1 2 f vn and the total number of vertices labeled with 1’s are given by (1)1 2 f vn . Therefore the total difference between the vertices la- beled with –1’s and 1’s is (1)(1)1 1 ff vv . The total number of edges labeled with –1’s are given by *(1)12 f en and the total number of edges labeled with 1’s are given by (1)12 f en . Therefore the total difference between the edges labeled with –1’s and 1’s is ** (1)(1) 0 ff ee , differ by zero. ** (1) 1(1)1 2 (1)(1)1 2 ff ff vvn een Thus in each cases we have (1)(1) 1 ff vv and ** (1)(1) 1 ff ee . 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 ,,, n Vvv v be the vertex set and 1 1in 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 :() {fV G When 0,1,3 (mod 4)n for 1in , 1; 1,2mod4 () 1;0, 3 mod4 i i fv i The edge labeling is given by * 11 1 1 ()()() 1() and()havesamesign 1() and()have different sign iii i ii ii fvv fvfv fv fv fv fv In view of the above labeling pattern we have, Table 1. Table 1. Vertex and edge conditions of a cycle graph. n (1) f v (1) f v (1) (1) ff vv 0mod4n 2n 2n 0 1mod4n 12n 12n 1 3mod 4n 12n 12n 1 n *(1) f e *(1) f e ** (1) (1) ff ee 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;2mod n Cn admits signed product cordial labeling. Theorem 2.4: The star graphadmits signed product cordial labeling. 1, , n Kn2 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 ,,,, nn Vvv vv 1i Ev :()fV G 11in ;2 1vin {1,1} for 1; 1mod2 () 1;0 mod2 i i fv i When n is even and odd, the edge labeling is given by * 12 * 12 1 ()1 ()1;1 i i fvv 2 f vvi n and * 12 * 12 1 ()1;112 ()1;112 i i fvvi n fvvin 1 respectively. In view of the above labeling pattern we have, Table 2. Hence the star graph 1,n K 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 . , nn PC ,nn Theorem 3.1: The Path graph admits signed product cordial labeling. B , n Pn 3 1 Proof: Let 123 and 123 be the vertex sets of the path graph and the edge set is given by ,, n vvvv,, n uuu u n P 11 2 ;11 ,;1 ii ii EvvinEvuin The graph n has 2n vertices and edges. To define vertex labeling the following P2n 1,1}:() {fV G Table 2. Vertex and edge conditions of a star graph. n (1) f v (1) f v (1) (1) ff vv 0mod2n 12n 12n 1 1mod2n 12n 12n 0 n *(1) f e *(1) f e ** (1) (1) ff ee 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 mod4 i i fv i 1; 1mod2 () 1;0m o d2 i i fu i The edge labeling are defined as follows for 11in 11 1 1 ()()() 1if() and() have samesign 1 if()and()havedifferentsign iii i ii ii fvvfvfv fv fv fv fv for 1in 1 1 () ()() 1if() and()havesame sign 1if()and()havedifferentsign iii i ii ii fvu fvfu fv fv fv fv Case 2: When n is odd The vertex labeling is given by for 12in 1;1,2m o d4 () 1;0, 3 mod4 i i fv i 1 ()1;() nn fvfv 1 for 11in 1; 1mod2 () 1;0m o d2 () 1 i n i fu i fu The edge labeling are defined as follows for 11in * 11 1 1 ()()() 1if() and()havesamesign 1 if()and()havedifferentsign iii i ii ii fvv fvfv fv fv fvfv for 1in * 1 1 () ()() 1if() and() have same sign 1if()and()havedifferent sign iii i ii ii fvu fvfu fv fv fv fv In view of the above labeling pattern we have, Table 3. Hence the graph admits signed product cordial labeling. , n Pn 3 3 Theorem 3.2: The graph admits signed product cordial labeling except for , n Cn n2mod 4. Copyright © 2011 SciRes. AM J. B. BABUJEE ET AL. 1528 Table 3. Vertex and edge conditions of the graph . , 3 n Pn n (1) f v (1) f v (1) (1) ff vv 0mod2n n n 0 1mod4n n n 0 3mod 4n n n 0 n *(1) f e *(1) f e ** (1) (1) ff ee 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 ,, n vvvv ,, n uuu u 3,Cn 11 1 2 ;1 1 ;1 ii n ii Evvinvv Evuin nn The vertex labeling is defined by for 1in 1; 1,2mod4 () 1; 0, 3 mod4 i i fv i 1; 1mod2 () 1;0m o d2 i i fu i The edge labeling is given by for 1in * 11 1 1 ()()() 1if() and()have same sign 1 if()and()havedifferent sign iii i ii ii fvv fvfv fv fv fv fv 1 * 1 1 1if()and()havesame sign () 1if()and()havedifferent sign ii nii fv fv fvv fv fv 1 * 1 1()and()havesame sign () 1()and()havedifferent sign ii ii ii fv fv fvu 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) f v (1) f v (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 f vvnn (1)e (1)e . Therefore the total difference between the edges labeled with –1’s and 1’s is (1)(1) 0 ff ee , differ by zero. (1) (1) (1) (1) ff ff vv ee n n Hence the cycle graph admits signed prod- uct cordial labeling. , n Cn 3 2 2 Theorem 3.3: The graph admits signed product cordial lab e ling. ,, nn Bn Proof: The graph , is a bistar obtained from two disjoint copies of 1,n , nn Bn K by joining the centre vertices by an edge. It has 2n + 2 vertices and 2n + 1 edges. Let 123 22 ,,,vvv ,n v be the vertices of the bistar graph. The edge set is defined as 1121 222 ;1 , ;2 1 i i Evvin Evv in We now define vertex labeling as :() {1,1}fVG 2 21 1;1mod2;12 () 1;0 mod2;322 ()1 ()1 i n ii fv ii fv fv n n 1 1 The edge labeling is given by 22 12 1 12 1 ()1;2 ()1 ()1;1 i n i f vvi n fvv fvvi n The total number of vertices labeled with –1’s are given by (1) 1 f vn 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)1 f vn (1)(1) 0 ff vv (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) 1 f en . Therefore the total difference between the edges labeled with –1’s and 1’s is (1)(1) 1 ff ee , differ by one. In view of the above labeling pattern we have, (1)(1) 11 (1)(1) 11 ff ff vv n ee n From the above labeling pattern we have (1)(1) 1 ff vv and (1)(1) 1 ff ee . Hence the bistar graph , admits signed product cordial labeling. ,, nn Bn2 Example 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. B Copyright © 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,fV1} ) Let where and . The vertex labeling for , is defined as 1 @(,TTmK VE 12 ,,, n uu u E T ()() VV 12 ,,, n Evu vuvu :{1,1}gV g vfvvV ,,,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 ,,, m u 12 uu () (1);1 i i g ui 12 (),(), ,( m . If then the sign of ()fv 1,) m g vug vug vu ), ,( ) m will be the sign of 12 (),( g ugu gu 12 (),(), ,( respectively and if f(v) = –1 then the sign of ) m g vug vug vu ,(),,() m will be the sign of 12 () g ugu gu . In both the cases the new m edges 12 ,,, m vu 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. ˆ 0n TP n P Theorem 4.6: If a tree T as signed product cordial labeling then where m is od d admits signed p rod- uct cordial labeling. ˆ 0n TP 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(, n TP VE ) where , n VV u 12 ,,uu and 1 ii u1;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. v Case 1: If 1 ()( )1fv fu , then the vertex labeling for the path graph follows from theorem 2.2 Case 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,3mod4 1;1,2m o d4 i fv i i Sub Case 2.2: when 2(mod4)n for 12in () 1;0,3mod4 1;1, 2 mod4 i fv i i and 1 ()1,() nn fv 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 ˆ 0n TP Corollary 4.7: If a connected graph G has signed product cordial labeling then the graph where n is odd admits signed product cordial labeling. ˆ 0n TP Theorem 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 , n u 12 ,,Vuu. Since G has a signed product cordial labeling there exists such :{1,1fV } that (1)(1) 1 ff vv and (1)(1) 1. ff ee Copyright © 2011 SciRes. AM J. B. BABUJEE ET AL. Copyright © 2011 SciRes. AM 1530 As 0mod4,n(1)(1) 0. ff vv 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 2 V 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 12 V :0mod i Vui ,:1 ii Vuu i VV 1:1mod2 i Vui 1 V GV 12 ,,, n uu u G n ;1 ii EEuu 2 ,E 12 ,,uu i this labeling pattern the graph admits signed prod- uct labeling where n is a multiple of . G 4 , n u 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. () () ii g ufu () 1when0mod2and() 1if0mod4 1when1mod2and()1if1mod4 1when0mod2and( )1if2mod4 1when1mod2and( )1if3mod4 i i i i i gu ifui ifui ifui ifui [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 () (). g uvf uvuvE () ii All the newly added edges g uu will share equally the labels –1 and 1 as per our construction above. Hence (1)(1) 0 gg vv and (1)(1) 0. gg ee Only by |