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
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





2
f
ufv





. f is called a mean cordial la-
beling if
 
1
ff
viv j and
 
1
ff
eie j,


,0,1,2ij, where


f
vx and denote the number of
vertices and edges respectively labelled with x (

f
ex
0,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



f
ufv. f is
called a cordial labeling if


1
ff
viv j and
 
1,
ff
eie 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

f
vx

f
ex
x


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



2
f
ufv


.
f
is called a mean cordial labeling of G if




1
ff
viv j

 and

1,
ff
eie j


,0,1,2ij where


f
vx and


f
ex 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


0
f
v 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





 
12
VGVG 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
  
012
fff
vvv 
p

p

02
f
p
e 

,

11
2
f
e,





21
2
f
e


p
 .
Therefore this labeling is a mean cordial labeling of G*.
Theorem 2.5: Any Path is a mean cordial.
n
P
*Associate professor (retired).
C
opyright © 2012 SciRes. OJDM

R. PONRAJ ET AL. 146
Proof: Let be the Path .
n
P
n12 n
uu u
Case (1):

0 mod 3
3.t

Let Define n2,1
i
f
uit

,

1, 1
ti
f
ui
t

0, 1 , 2ti
f
uit


. Then
and
 
01
ff
vv
 

2
f
vt

01,1 2
fff
etee .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 
n
u
0,et
   
012
fff
vvv

2.t
 
1
ff
ee
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 n
u. Here
nt

1uin 
 


011,2
ff f
vvtv ,t

 

f and

e11.t


02
ff
eet. Hence f is a mean
cordial labeling.
Illustration 2.6: Mean cordial labeling of is
shown in Figure 1.
6
P
Theorem 2.7: The Star 1,n
K
is a mean cordial iff
.
2n
Proof: Let and


1, ,:1 ni
VKuui n

:1 .ui n

1,ni
EK 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

2
f
e
Case (2):
In this case again a contradiction.

0e0
f,
,
Case (3):

1.fu

0e Here also a contradiction. 0
f
Hence 1,n
K
is not a mean cordial for all 2.n
Theorem 2.8: The cycle is mean cordial iff
.
n
C
uu

1,2 mod 3nC
Proof: Let be the cycle
n
0n12 1n
uu
Case (1):

mod 3
t

Let . Then . In this
case a contradiction
3n

0
f
e
n
 
012
fff
vvv 

od 3
t
1,t
1 mCase (2):
Let Define
31.nt

0,1 1
i
f
uit

1,1
1ti
f
ui
 t

2, 1 , 21ti
f
uit
t
 
Then

01
f
vt,
 
12
ff
vv

 and
2 1 2
2 2
1
1
0
0
0
1


01,t
f
v




12
ff
vv t and
Figure 1. Mean cordial labeling of P6.
Then


11et
f

,




02.
ff
eet

 Hence f is a m
Case (3):
ean cor-
dial labeling.


mod 3
2
2n
Let 3nt

. Define

0,1 1
i
f
uit,


1, 1
1ti
f
uit


,


2,11
21ti
f
uit
Then



1
f
vt,





02
ff
vvt1

 and


11et
f

,




02.eet
ff

 Hence f is a mean cor-
he Complete graph
dial labeling.
Theorem 2.9: Tn
K
is mean cor-
dial iff 2.n

Proof: Clearly 1
K
and 2
K
are mean cordial by
Theorem 2.5. Assu2.n possible let there be a
mean cordial labeling f.
Case (1):
me If


3
, 1.t
0 modn
Let 3nt

 Then
 


012
fff
vvvt 

t

02
f
e

,
t


22
12
f
et t



 , and

2
22
f
t
et




 . Then a con-
tradiction.
Case (2):
 
2
102
ff
ee t1,


1 mod 3n
1
Let 3nt


Subcase (i ) :


01
f
vt






12
ff
vvt
1t

02
f
e




,
 
11
2
f
et
tt
t
 1t



 and

2
22
f
t
et




 ,


2
12 2
ff
ee tt1,

 a contra-
diction.
Subcase ( i i ) :


11
f
vt


1t

 
02
ff
vvt
t

02
f
t
e 

,
 
2
11
2
f
et t



 and
 
21
2
f
t
et
 t



 .


2
20
ff
eett1, a con-
tradiction.
Subcase (iii):


21
f
vt


t

t
 
01
ff
vv

0,
2
f
t
e 


2
11
2
f
et
tt



 and
 
1
21
2
f
t
et

 .t



 Then




102
ff
ee tt
21,

 a contradiction.
Case (3):


2 mod 3n
Let 32nt


Subcase ( i) :


0
f
vt

 
12
ff
vv t
1

1

1t

02
f
t
e 

,
 
11
2
f
et tt
t



 and
 
2
1
21
2
f
t
et





 . Then

R. PONRAJ ET AL. 147
 
2
1023
ff
ee tt

1vt
1,
a contradiction
Subcase ( i i ) :
f


02
ff
vvt
t

1
1 t
t
1,
1

1tt
1,

1
02
f
t
e



, and

2
11
2
f
et t


 
1
21
2
f
t
et




 . Then
 
2
20
ff
eett

2vt
a contradiction.
Subcase (iii):
ft
 
01
ff
vvt
1


1
02
f
t
e




2
f
t
et




and
 
2
11
2
f
et 



21 t
2

Then a contradic-
tio
 
2
10 1
ff
eet tt
n.
Theorem 2.10: The Wheel is not a mean cordial
gr
n
W
aph for all n
Proof: Let W where n C is the cycle
12 1n
uu uu and

1
VK If possible let there be a
me labeling f.
3.
1nn
CK
. u
an cordial
e (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 1
f
et
Subcase ( i i ) : .
12t

1or 2fu
In this case gain a contradiction.

0,et a
f
1 mod 3nC ase (2):

Let 31nff etet 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. ), w
Theorem 2.11:

1, n
SK is mean cordial, where S(G)
debdivision of G.



(i):
notes su
Proof:
Let and
 

1, ,, :1 nii
VSKuuvin



,:1
iii
ESKuuuvin
1,n
Case 

0 mod 3n
3.t
Let n
Define


0,fu

0,1,
i
f
uit

1,1 2
ti
f
ui
t

0,1,
i
,
f
vit



2,12 ,
ti
f
vi
t, Then

021
f
vt




122
ff
v
vt and

01
ff
ee

2,t




22
f
et.
o
Let
1
He ean crdial lbeling. nce f is a m
e (2):
a
Cas

1 mod 3
1 Assign labels to the vertices ,i uu and

11
i
vin  as in case (1). Then assign the label 1
and 2 to the vertices and v respectively. Here
n
3tn
n
un
and ,
  
0122
fff
vvv t

02
f
et




122
ff
ee 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
,i uu
1

) as in case (2). Then assign the
label 0 and 2 to the vertices, respectively. Here
n
un v




022
ff
vv t2,

 and

12v1
ft


122
f
et

,


2
ff
eet

02 1,

 Hence f is a
mean cordial labeling.
Illustration 2.12: Mean cordial labeling of


1,6
SK
is shown in Figure 2.
Theorem 2.13: The comb is mean cordial
where
1n
PK
12
GG

denotes the corona of and .
1
Proof: Let be the Path . Let
G
uu u 
2
G
n
P12 n






1nn
VP KVP:1
i
vi n

,






:1
ii
uvi n
1nn
EP KEP


Case (1):


0 mon
3.nt d 3 Let



2, 1
i
f
uit

,


1, 1
ti
f
ui
t


20, 1 ti
f
ui
t

,


2,1
i
f
vit


1, 1
ti
f
vi
t

,


20,1 ti
f
vi
t
Then




2
f
v01
ff
vv 2t

 and






122,
ff
ee t02
f
e t1,


Hence f is a mean cordial labeling.
Case (2):


d 31 mon
31nt Let


i
v1in . Assign labels to the vertices and ( 1
i
u


n
u
) as in case (1). Then assign the label 0
and 1 to the vertices and . Here
n
v






1,22
f
v012
ff
vv t,t and




022,
ff
ee t and

121
f
et
Hence f is a mean cordial labeling.
Case (3):


d 32 mon
32.nt Let


i (1in Assign labels to the vertices i
u &
v2

) as in case (1). Then assign the label 0,
2 and 0, 1 to the vertices u and respec-
tively. Here
1, n
u
nn1, n
vv



02
f
vt2,

 and
 
122t1
ff
vv






01
fff
eee221.t

 Hence f is a mean cor-
dial labeling.
Theorem 2.14: PnΘ2K1 is mean cordial.
0
1
1
1
1
1
11
1
0
0
0
0
0
0
0
2
2
2
2
2
2
2
2
0
Figure 2. Mean cordial labeling of S(K1,6).

R. PONRAJ ET AL. 148
Let




2, ,, :1 ni
VKuvui n

 and
Proof: Let Pn be the Path 12 Let vi and wi be
the pendant vertices which are adjacent to
.
n
uu u
,1 .
i
uin






2, ,:1 nii
EKuuvuin

 . 2,1
K
and 2,2
K
are mean
cordial by Theorem 2.5 and 2.8 respectively. Assume
. Suppose f is a mean cordial labeling of 2,n 2n
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, 12
in
fu i
2
1, 12
ni
n
fu i








0 mod 3nCase (1):

0, 12
in
fv i


3.tn

Then 0or
f
ett
Let 1, a contradiction
since the size of 2,n
K
is 6.t

1, 12
in
fw i


od 31 mnCase (2): ce
Let n = 3t + 1. Here again a contradic-
tion.

0
ft,
2
2, 12
ni
n
fv i





 Case (3):


2 mod 3n


0or
f
ett
2,n
Let n = 3t + 2. Here 1, again a con-
tradiction to the size of
K
.
2
2, 12
ni
n
fw i






3. Conclusion
Then and
  
012
fff
vvv
 
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

1
0, 12
in
fu i


1
2
1
1, 12
ni
n
fu i

 




4. Acknowledgements

3
0, 12
in
fvi   The authors are thankful to the referee for their valuable
comments and suggestions.

3
1, 12
in
fwi 
REFERENCES
11
22
0
nn
fv fw

 

 
 
 
[1] J. A. Gallian, “A Dynamic Survey of Graph Labeling,”
Electronic Journal of Combinatorics, Vol. 18, 2011, pp.
1-219.
11
22
1, 2
nn
fv fw

 

 
 
 
[2] I. Cahit, “Cordial Graphs: A Weaker Version of Graceful
and Harmonious Graphs,” Ars Combinatoria, Vol. 23, No.
3, 1987, pp. 201-207.
11
22
1
2, 12
nn
ii
n
fv 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
  
012
fff
vvv
 
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,n
K
is a mean cordial iff 2.n

Proof: