Ratio Mathematica Volume 42, 2022

On integer cordial labeling of some families
of graphs

S Sarah Surya*
Alan Thomas †

Lian Mathew ‡

Abstract

An integer cordial labeling of a graph G(p, q) is an injective map f :
V → [−p

2
...p

2
]∗ or [−⌊p

2
⌋...⌊p

2
⌋] as p is even or odd, which induces an

edge labeling f∗ : E → {0, 1} as f∗(uv) =

{
1, f(u) + f(v) ≥ 0
0, otherwise

such that the number of edges labelled with 1 and the number of edges
labelled with 0 differ at most by 1. If a graph has integer cordial la-
beling, then it is called integer cordial graph. In this paper, we have
proved that the Banana tree, K1,n ∗ K1,m, Olive tree, Jewel graph, Ja-
hangir graph, Crown graph admits integer cordial labeling.

Keywords: Banana tree, K1,n ∗ K1,m, Olive tree, Jewel graph, Ja-
hangir graph, Crown graph, Integer cordial labeling.

2020 AMS subject classifications: 05C78 1

*Department of Mathematics, Stella Maris College(Autonomous), Chennai, Affiliated to the
University of Madras, India; e-mail: sara24solomon@gmail.com.

†Department of Mathematics, St. Aloysius College, Edathua, India; e-mail: alanam-
palathara@gmail.com.

‡Department of Mathematics, Stella Maris College(Autonomous), Chennai, Affiliated to the
University of Madras, India; e-mail: lianmathew64@gmail.com.
1Received on January 28th, 2022. Accepted on June 9th, 2022. Published on June 30th, 2022.
doi: 10.23755/rm.v39i0.709. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper
is published under the CC-BY licence agreement.

105



S Sarah Surya, Alan Thomas, Lian Mathew

1 Introduction
Let G be a simple, finite, undirected graph. For terms not defined here, we refer to
Harary [3]. A graph labeling is an assignment of integers to the vertices or edges,
or both, under some conditions. It has wide applications in mathematics as well
as in other fields such as circuit design, communication network addressing, date
base management and so on. In this paper, we have proved that the Banana tree,
K1,n ∗ K1,m, Olive tree, Jahangir graph, Jewel graph, Crown graph are integer
cordial.

2 Preliminaries
Definition 2.1 [8] A mapping f : V (G) → {0, 1} is called binary vertex la-
beling of G and f(v) is called the label of the vertex v of G under f. If for
an edge e = uv, the induced edge labeling f∗ : E(G) → {0, 1} is given by
f∗(e) = |f(u) − f(v)|.
Definition 2.2 [1] A binary vertex labeling of a graph G is called a cordial labeling
if |vf(0) − vf(1)| ≤ 1 and |ef(0) − ef(1)| ≤ 1, where vf(i) = number of vertices
having label i under f and ef(i) = number of edges having label i under f∗. A
graph G is cordial if it admits cordial labeling. I. Cahit [1] introduced the concept
of cordial labeling as a weaker version of graceful and harmonious graphs.
Definition 2.3 [7] An integer cordial labeling of a graph G(p, q) is an injective
map f : V → [−p

2
...p

2
]∗ or [−⌊p

2
⌋...⌊p

2
⌋] as p is even or odd, which induces an

edge labeling f∗ : E → {0, 1} defined by f∗(uv) =

{
1, f(u) + f(v) ≥ 0
0, otherwise

such

that the number of edges labelled with 1 and the number of edges labelled with 0
differ at most by 1. If a graph has integer cordial labeling, then it is called integer
cordial graph.
Definition 2.4 [4] A banana tree Bn,k is a graph obtained by connecting one leaf
of each of n copies of a k - star graph with a single root vertex. It has nk + 1
vertices and nk edges.
Definition 2.5 [5] K1,n ∗ K1,m is the graph obtained from K1,n by attaching root
of a star K1,m at each pendant vertex of K1,n.
Definition 2.6 [6] Olive tree Tk is a rooted tree consisting of k branches where the
i th branch is a path of length i and it consists of k(k+1)

2
+ 1 vertices.

Definition 2.7 [5] The Jewel graph Jn is the graph with vertex set V (Jn) =
{u, v, x, y, wi : 1 ≤ i ≤ n} and edge set E(Jn) = {ux, uy, xy, xv, yv, uwi, vwi :
1 ≤ i ≤ n}.
Definition 2.8 [2] Jahangir graph Jn,m for m ≥ 3, is a graph on nm + 1 vertices,
consisting of a cycle Cnm with one additional vertex which is adjacent to m ver-

106



On integer cordial labeling of some families of graphs

tices of Cnm at a distance n to each other on Cnm.
Definition 2.9 [5] The crown Cn

⊙
K1 is the graph obtained from a cycle by at-

taching a pendant edge to each vertex of the cycle.

In [7], Nicholas et al. introduced the concept of integer cordial labeling of graphs
and proved that some standard graphs such as Path Pn, Star graph K1,n, Cycle Cn,
Helm graph Hn, Closed helm graph CHn are integer cordial. Kn is not integer
cordial, Kn,n is integer cordial iff n is even and Kn,n\M is integer cordial for
any n, where M is perfect matching of Kn,n. In [8], Sarah et al. proved that the
Sierpinski Sieve graph, the graph obtained by joining two friendship graphs by a
path of arbitrary length, (n, k)− kite graph and Prism graph are integer cordial.

3 Main Results

Theorem 3.1. Banana tree Bn,k is integer cordial.

Proof. Case1: When n is even (the total number of vertices is odd).
Let u denote the root vertex. Let v1, v2, . . . , vnk

2
denote the vertices on n

2
leaves

and vnk
2
+1, vnk

2
+2, . . . , vnk denote the vertices on the remaining

n
2

leaves of Bn,k.
We define f : V → [−⌊p

2
⌋...⌊p

2
⌋] as follows:

f(u) = 0

f(vi) = −i; 1 ≤ i ≤
nk

2

f(vi) = i −
nk

2
;
nk

2
+ 1 ≤ i ≤ nk

Case 2: When n is odd and number of vertices is odd.
Let u denote the root vertex. Let v1, v2, . . . , v(n−1)k

2

denote the vertices on ⌊n
2
⌋

leaves and v(n−1)k
2

+1
, v(n−1)k

2
+2
, . . . , v(n−1)k denote the vertices of remaining ⌊n2 ⌋

leaves. Let u1, u2, . . . , uk denote the k vertices of the another leaf such that u1 is
adjacent to u and uk is adjacent to ui where 1 ≤ i ≤ k.

107



S Sarah Surya, Alan Thomas, Lian Mathew

We define f : V → [−⌊p
2
⌋...⌊p

2
⌋] as follows:

f(u) = 0

f(vi) = −i; 1 ≤ i ≤
(n − 1)k

2

f(vi) = i −
(n − 1)k

2
;
(n − 1)k

2
+ 1 ≤ i ≤ k(n − 1)

f(ui) = −(
nk

2
+ 1 − i); 1 ≤ i ≤

k

2

f(ui) =
k(n + 1)

2
+ 1 − i;

k

2
+ 1 ≤ i ≤ k

Case 3: When n is odd and the number of vertices is even.
Let u denote the root vertex. Let v1, v2, . . . , v(n−1)k

2

denote the vertices on ⌊n
2
⌋

leaves and v(n−1)k
2

+1
,v(n−1)k

2
+2

,...,vk(n−1) denote the vertices of another ⌊n2 ⌋ leaves
where v1 not adjacent to u. Let u1, u2, ..., uk denote the k vertices of the remaining
leaf such that u1 is adjacent to u and uk is adjacent to ui, 1 ≤ i ≤ k.
We define f : V → [−p

2
...p

2
]∗ as follows:

f(u) = 1

f(vi) = −i; 1 ≤ i ≤
(n − 1)k

2

f(vi) = i + 1 −
(n − 1)k

2
;
(n − 1)k

2
+ 1 ≤ i ≤ k(n − 1)

f(ui) = −
(
⌈
nk

2
⌉ + 1 − i

)
; 1 ≤ i ≤ ⌈

k

2
⌉

f(ui) =
k(n + 1)

2
+ 2 − i; ⌈

k

2
⌉ + 1 ≤ i ≤ k

Hence in all the possible cases, we have |ef(1) − ef(0)| ≤ 1. Therefore, Banana
tree Bn,k admits integer cordial labeling(See Figure 1).

Theorem 3.2. The graph K1,n ∗ K1,m is integer cordial.
Proof. Case 1: When n is even and m can be either odd or even.
Let u1, u2, ...un

2
(1+m) be the vertices of

n
2

leaves and let w1, w2, ...wn
2
(1+m) be the

vertices of the other n
2

leaves and let u0 be the center vertex.
We define f : V → [−⌊p

2
⌋...⌊p

2
⌋] as follows.

f(u0) = 0

f(ui) = i, 1 ≤ i ≤
n

2
(1 + m)

f(wi) = −i, 1 ≤ i ≤
n

2
(1 + m)

108



On integer cordial labeling of some families of graphs

Figure 1: Integer cordial labeling of B3,5

Case 2: When n is odd.
Let the center vertex be u0. Let u1, u2, ...u⌊ n

2
⌋(1+m) be the vertices of ⌊n2 ⌋ leaves

and let w1, w2, ...w⌊ n
2
⌋(1+m) be the vertices of the other ⌊n2 ⌋ leaves and let v1, v2, ...v(m+1)

be the remaining vertices on the left out leaf, where v1 is adjacent to u.
Case 2.1: When m is odd.
We define f : V → [−⌊p

2
⌋...⌊p

2
⌋] as follows:

f(u0) = 0

f(ui) = i, 1 ≤ i ≤ ⌊
n

2
⌋(1 + m)

f(wi) = −i, 1 ≤ i ≤ ⌊
n

2
⌋(1 + m)

f(v1) = −
(
⌊
n

2
⌋(2 + m)

)
f(vi) = ⌊

n

2
⌋(1 + m + i), 2 ≤ i ≤ ⌊

m + 1

2
⌋

f(v⌊ m+1
2

⌋+i) = −⌊
n

2
⌋(1 + m + i), ⌈

m + 1

2
⌉ ≤ i ≤ m + 1

Case 2.2: When m is even.
We define f : V → [−p

2
...p

2
]∗ as follows:

f(u0) = 1

f(ui) = i + 1, 1 ≤ i ≤ ⌊
n

2
⌋(1 + m)

f(wi) = −(i + 1), 1 ≤ i ≤ ⌊
n

2
⌋(1 + m)

f(v1) = −1

f(vi) = ⌊
n

2
⌋(1 + m + i), 2 ≤ i ≤

m + 1

2

f(v⌊ m+1
2

⌋+i) = −
(
⌊
n

2
⌋(1 + m + i)

)
,
m + 1

2
≤ i ≤ m + 1

109



S Sarah Surya, Alan Thomas, Lian Mathew

Here, for all possible cases, we have |ef(1) − ef(0)| ≤ 0. Therefore K1,n ∗ K1,m
is integer cordial(See Figure 2).

Figure 2: Integer cordial labeling of K1,3 ∗ K1,3

Theorem 3.3. Olive tree Tk admits integer cordial labeling.

Proof. Let Ui denote the (k + 1 − i)th branch and U denote the root vertex.
Case 1: When k(k+1)

2
+ 1 is an odd number.

An integer cordial labeling of Tk is obtained by assigning the positive integer from
1 to k(k+1)

4
to the vertices of the branches namely U2, U3, U6, U7, U10, U11, U14,...,

in any order and the negative integers from −1 to −k(k+1)
4

to the vertices of the
branches namely U1, U4, U5, U8, U9, U12, U13, ..., in any order and let U = 0.

Case 2: When k(k+1)
2

+ 1 is an even number.
An integer cordial labeling of Tk is obtained by assigning the positive integers
from 2 to (k(k+1)+2)

4
to the vertices of the branches namely U2, U3, U6, U7, U10, U11, ...,

in any order and the negative integers from −1 to −(k(k+1)+2)
4

to the vertices of the
branches namely U1, U4, U5, U8, U9, U12, U13, ..., in any order and let U = 1.
Hence, we have |ef(1) − ef(0)| ≤ 1. Therefore, Olive tree admits integer cordial
labeling(See Figure 3).

Theorem 3.4. The Jewel graph Jn admits integer cordial labeling.

Proof. Let V (Gn) = {u, v, x, y, wi : 1 ≤ i ≤ n} and E(G) = {ux, uy, xy, xv, yv, uwi, vwi :
1 ≤ i ≤ n}.
Case 1: When n is even.

110



On integer cordial labeling of some families of graphs

Figure 3: Integer cordial labeling of T4

We define f : V → [−p
2
...p

2
]∗ as follows:

f(u) = 1

f(v) = −1
f(x) = 2

f(y) = −2

f(wi) = i + 2, 1 ≤ i ≤ ⌊
n

2
⌋

f(wi) = −(i − ⌊
n

2
⌋ + 2), ⌈

n

2
⌉ ≤ i ≤ n − 1

Case 2: When n is odd.
We define f : V → [−⌊p

2
⌋...⌊p

2
⌋] as follows:

f(u) = 1

f(v) = −1
f(x) = 2

f(y) = −2

f(wi) = i + 2, 1 ≤ i ≤ ⌊
n

2
⌋

f(wi) = −(i − ⌊
n

2
⌋ + 2), ⌈

n

2
⌉ ≤ i ≤ n − 1

f(wn) = 0

Here, for both the cases, we have n + 3 edges with label 1 and n + 2 edges with
label 0. Hence in all possible cases, we have |ef(1) − ef(0)| = 1. Therefore, Jn
is integer cordial(See Figure 4).

Theorem 3.5. Jahangir graph Jn,m is integer cordial except when n = 1.

111



S Sarah Surya, Alan Thomas, Lian Mathew

Figure 4: Integer cordial labeling of J3

Proof. When n = 1, we have J1,m to be a complete graph with m+1 vertices and
hence not integer cordial.
Let u denote the central vertex adjacent to m vertices of Cnm and let v1, v2, ..., vnm
denote the vertices in the cycle Cnm.

Case 1: When the number of vertices (nm + 1) is odd.
We define f : V → [−⌊p

2
⌋...⌊p

2
⌋] as follows:

f(u) = 0

f(vi) = i; 1 ≤ i ≤
nm

2

f(v( nm
2

+i) = −i; 1 ≤ i ≤
nm

2

Case 2: When the number of vertices (nm + 1) is even.
We define f : V → [−p

2
...p

2
]∗ as follows.

f(u) = 1

f(vi) = i + 1; 1 ≤ i ≤ ⌊
nm

2
⌋

f(v⌊ nm
2

⌋+i) = −i; 1 ≤ i ≤ ⌈
nm

2
⌉

Hence in all possible cases, we have |ef(1) − ef(0)| ≤ 1. Therefore Jn,m admits
integer cordial labeling except when n = 1(See Figure 5).

Theorem 3.6. The Crown Cn
⊙

K1 admits integer cordial labeling.

112



On integer cordial labeling of some families of graphs

Figure 5: Integer cordial labeling of J2,4

Proof. Let v1, v2, ..., vn be the vertices of the inner cycle and let u1, u2, ..., un be
the pendent vertices where ui is adjacent to vi.
We define f : V → [−p

2
...p

2
]∗ as follows:

f(vi) = −i
f(ui) = i

Here, we have n edges with label 1 and n edges with label 0. Hence, |ef(1) −
ef(0)| = 0. Therefore, the Crown Cn

⊙
K1 is integer cordial(See Figure 6).

Figure 6: Integer cordial labeling of C4
⊙

K1

4 Conclusion
In this paper, we proved that the Banana tree, K1,n ∗ K1,m, Olive tree, Jewel

graph, Jahangir graph, Crown graph are integer cordial. Obtaining the integer
cordial labeling of other class of graphs is still open. Further investigation can be
done for all the networks.

113



S Sarah Surya, Alan Thomas, Lian Mathew

References
[1] I. Cahit, Cordial graphs, A weaker version of graceful and harmonious graphs,

Ars Combinatoria, 1987, Vol 23, 201 – 207.

[2] Gao, W., A. S. I. M. A. Asghar, and Waqas Nazeer, Computing degree-based
topological indices of Jahangir graph, Engineering and Applied Science Let-
ters, 2018, 16-22.

[3] F. Harary, Graph theory, Addison Wesley, Reading, Massachusetts, 1972.

[4] Lokesha, V., R. Shruti, and A. Sinan Cevik, M-Polynomial of Subdivision
and complementary Graphs of Banana Tree Graph, J. Int. Math, Virtual Inst,
2020, 157-182.

[5] Lourdusamy, A., and F. Patrick, Sum divisor cordial graphs, Proyecciones
(Antofagasta), 2016, 119-136.

[6] Marykutty P. T., and K. A. Germina, Open distance pattern edge coloring of a
graph, Annals of Pure and Applied Mathematics, 2014, 191-198.

[7] T. Nicholas and P. Maya, Some results on integer cordial graph, Journal of
Progressive Research in Mathematics (JPRM), 2016, Vol 8, Issue 1,1183-
1194.

[8] S. Sarah Surya, Sharmila Mary Arul, and Lian Mathew, Integer Cordial La-
beling for Certain Families of Graphs, Advances in Mathematics: Scientific
Journal, 2020, no.9, 7483–7489.

114