Applied Mathematics, 2011, 2, 1525-1530
doi:10.4236/am.2011.212216 Published Online December 2011 (http://www.SciRP.org/journal/am)
On Signed Product Cordial Labeling
Jayapal Baskar Babujee, Shobana Loganathan
Department of Mat hematics, Anna University, Chennai, India
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

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
Kn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
,,,,
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
P2n
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

n2mod 4.

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
vvnn
(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
Bn2
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

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
,,,
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
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

 

J. B. BABUJEE ET AL. 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