C:/Users/welcome/Desktop/AIP/Some Results on Odd Even Congruence Labeling of Graphs/LaTeX-OddEven-Labeling.dvi


Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

141 
https://internationalpubls.com 

Some Results on Odd-Even Congruence Labeling of Graphs 

G.Thamizhendhi
1 and K. Kanakambika

2*

 

1Department of Mathematics, Sri Vasavi College, Erode-638 316, Tamilnadu, India. 

gkthamil@gmail.com 
2*Department of Mathematics, Vellalar College for Women (Autonomous), Erode-638 102, Tamilnadu, India. 

Email:kkanakambikavel@gmail.com 

 

Article History: 

Received: 05-10-2023 

Revised: 15-11-2023 

Accepted: 02-12-2023 

Abstract:  

Introduction: Labeling of graphs has been introduced in 1966. Assignment of natural 

numbers to vertices and/or edges is referred as graph labeling. Inspired by the ample 

application of graph labeling technique in real life problems, multifarious labeling strategy 

was adopted and investigated by many researchers. 

Objectives:Graph labeling plays a vital role in various fields and can be implemented 

in multitudinous discipline including coding theory, X-ray, Psychology, crystallography, 

circuit design, communication networks, astronomy, radar, data security, secret sharing, 

data base management and so on. Apart from these labeling techniques serve as a model 

to understand discrete mathematical domains. 

Methodology:In this paper, an attempt has been made to introduce new labeling such as o

dd-even congruence labeling. Congruence Graph Labeling is an allocation of natural 

numbers as labels for the edges and vertices of a graph based on modular arithmetic 

property. Odd-even congruence labeling is an allocation of odd integers to vertices and 

even integers to edges in addition to congruence graph labeling. 

Result: The suggested labeling has been identified on complete bipartite graph, comb 

graph and spliting graph of a star graph. Further, it is proved that 

graph acquired by connecting two copies 

of even cycle Cr by a path Pt, K1,t⊗P2 and D2 (Pt) are odd-even congurence graph. 

Keywords: Labeling, Congruence labeling, Odd-even congruence labeling, Tensor graph. 

 

1. Introduction 

The relation between any of the objects in the real world can be represented as graphs, whose 

structures, properties, interrelations and correlations are interpreted in Graph Theory. The graph 

comprises of dots associated by lines which are referred as vertices and edges respectively. It aids the 

researchers to frame the hypothesis and establish the solution certainly. 

Graph labeling was procured as the most prominent one among the multifarious conception of graph 

theory to design the graphical model of the real life situations. In the middle of 19th century, A.Rosa 

introduced graph labeling[8]. The vertices and edges of the graphs are labeled with natural numbers 

with certain constraints in order to discriminate individually. Inspired by its comprehensive application 

in modeling all the circumstances, numerous labeling technique has been proposed and overworked by 

several researchers.  

In this paper, a new labeling procedure named odd-even congruence labeling is established based on 

modular division. A graph G is identified as odd-even congruence graph, if its vertex set and edge set 

are tagged with distinct odd and even integers respectively, further  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

142 
https://internationalpubls.com 

f (sp) ≡ f (sq)(mod g (w)), sp and sq are adjacent vertices in G. This paper is devoted for investigating 

the existence of odd-even congruence graphs of complete bipartite graph, Comb graph and spliting 

graph of a star graph. In addition, graph acquired by connecting two copies of even cycle Cr by a path 

Pt, the tensor product of K1,t & P2 and the shadow graph of the path Pt are proved as odd-even 

congruence graph. 

2. Preliminaries 

Definition 2.1[2] Bipartite graph G [X,Y ] is recognized as complete bipartite graph Kr,t , the edges 

occur in between every distinct pair of spf q such that sp ∈ X and f q ∈ Y . 

Definition 2.2[4] Comb graph Pt ⊙ K1 is constructed by introducing single pendent edge to link all 

the vertices in Pt. 

Definition 2.3[7] In a graph G(V, E), if the edge set is E = {spf / sp f ∈ V & sp /= f} and f  is a fixed 

vertex then G is stated as a star graph, it is denoted by St. 

Definition 2.4[5] The spliting graph, Spl(G) is arrived by introducing a new vertex fp for each 

existing vertex sp moreover N (sp) = N (fp), where N (sp) is the neighborhood of sp. 

Definition 2.5[11] Tensor product G1 ⊗ G2 of G1 and G2 is a graph whose vertices and edges a re  

V (G1 ⊗ G2) = V (G1) × V (G2) and E(G1 ⊗ G2) = {(s1, s2)(s3, s 4)|s1s3 ∈ E(G1) and s2s4 ∈ E(G2)}. 

Definition 2.6[12] Shadow graph D2 (G) is constituted by picking 𝐺′and 𝐺′′alike G and introduce 

edges in between 𝑠′∈ 𝐺′and 𝑠′′∈ 𝐺′′where 𝑠′′ is the neighbors of parallel vertex of 𝑠′. 

Definition 2.7[13] A bijection h : V → {1, 2, ....d} and  k : E → {1, 2,….d − 1}of G is claimed as 

congruence graph, if h (sp) ≡ h (sq)(mod k (wp)), where d = min {2 |V | , 2 |E |}. 

Definition 2.8[14] A bijection h : V → {1, 2, ....2d+1} and  k : E → {2,4,….2d} of G is referred as 

odd-even congruence graph, if h (sp) ≡ h (sq)(mod k (wp)), where d = min {2 |V | , 2 |E |}. 

3. Main Results 

In this section, simple finite connected graph G = (V, E) with |V | = r and |E| = t were considered and 

proved that it admits odd-even congruence labeling. 

Theorem 3.1 Every Kr,t is odd-even congruence graph for r ≥ 1, t ≥ 1. 

Proof: 

Consider,  Km,n with |V | = r + t and |E| = rt.  

d = min {2 |V | , 2 |E |} 

For G = Kr,t we have, 

d = min {2 (r + t), 2rt} 

 = 2 (r + t) 

there exist two independent and disjoint vertex sets such as  

V1 = {s1, s2,…sr} and V2 = {f1, f2, ....ft}. The edge set be E = {w1, w2,…wrt}. 

where w1 = s1f1,  w2 = s2f1, ......., wm = srf1, ..., er+1 = s1f2,…., ert = srft. 

Bijection h : V (G) → {1, 3,…., 4r + 4t + 1} 

and k : E (G) → {2, 4,…., 4m + 4n}  is defined as 

V1 : h (sp) = 2p − 1, for all p = 1 to r 

V2 : h (f q) = 2r (t + 1) – 2r q + 1, for all q = 1 to t and 

k (wl) = 2rt − 2 (l − 1), for all l = 1 to rt 

To prove the existence of odd-even congruence labeling, consider 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

143 
https://internationalpubls.com 

 
 

10 
 

26 
24 

30 28 22 

10 
20  16 14 12 

18 
 

 

 

h (sp) − h (f q) ≡ (mod k (wp)) 

(2p − 1) − (2rt + 2r – 2r q + 1) ≡ (mod (2rt − 2l + 2)) 

(2rt − 2l + 2) divides (2p − 1 – 2rt – 2r + 2r q − 1) for all p and q.  

Hence, every complete bipartite graph is odd-even congruence graph. 

Example 3.2 

Consider the graph G = K3,2 with |V1 | = 3 and |V2 | = 2. 

13 7 

 

 

12 2 

 

 

1 3 5 

Figure - 1 - K3,2 

The odd-even congruence labeling of Complete bipartite graph is revealed in Figure - 1.  

Suppose G = K4,4 with |V1 | = 4 and |V2 | = 4. 

33 25 17 9 

 

 

 

32 2 

 

 

 

 

1 3 5 7 

Figure - 2 - K4,4 

Figure - 2, shows that K4,4 receives odd-even congruence labeling 

Theorem 3.3 

Comb graph Pt ⊙ K1 is odd-even congruence graph, t ≥ 1. 

Proof: 

Let G = Pt ⊙ K1   with |V | = 2t and |E| = (2t − 1).  

Then d = min (2 (2t), 2 (2t − 1)) 

 = 4t − 2 

Let {sp/1 ≤ p ≤ t} and {fp/1 ≤ p ≤ t} are vertex sets, here fp represents pendent vertices. Further, wp 

= {spsp+1/1 ≤ p ≤ t − 1} are edges of Pt and edges adjacent to fp are denoted as 

{ep = spfq/1 ≤ p ≤ t}. 

Define the bijection h : V  → {1, 3, ..., 8t − 3} as  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

144 
https://internationalpubls.com 

h (s2p−1) = 4 (t − p) + 3  

h (s2p) = 4p − 1 

h (f2p−1) = 4p – 3 

h (f2p) = 4 (t − p) + 1 

where p = 1 to (t/2) if t is even 

  p = 1 to (t+1)/2 if t is odd 

The edge labeling k : E (G) → {2, 4, ..., 8t − 4} is defined as 

k (wp) = 4 (t − p),  p = 1 to t − 1 

k (ep) = 4 (t − p) + 2,  p = 1 to t 

Clearly, k (wi) divides ( h (s2p−1) − h (s2p)) and k (ep) divides ( h (sp) − h (fp)) 

Hence, the comb graph Pt ⊙ K1 is odd-even congruence graph. 

Example 3.4 

Consider a graph G = Pt ⊙ K1 with t = 10. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure - 3 - P10 ⊙ K1 

Figure - 3 exhibits the odd-even congruence labeling of the comb graph P10 ⊙ K1. 

Theorem 3.5 

Spliting graph of a star graph St is odd-even congruence graph. 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

145 
https://internationalpubls.com 

48 
20 

44 
40 36 32 28 

b 47 b 43 b 39 b b 35 

24 

b 31 

26 

b 27 

46 
42 38 

30 
34 

50 22 

 
 

18 

 
8 10 12 

14 
16 

 

Proof: 

Suppose G = Spl (St) is splitting graph with |V | = 2t + 2 and |E| = 3t.  

The vertex set be V (G) = {s, s1, s2, ...st} ∪ {f, f1, f2, ...ft} 

where, s, s1, s2, ...st is vertex  set of star graph and s is apex vertex  

           f, f1, f2, ...ft are the vertices added to form G. 

Also the edge set be 

E (G) = {w1, w2, ..., wt, wt+1, ...., w2t, w2t+1,…, w3t} 

here, w1, w2, ..., wt are the edges of Sn, wt+1, ...., w2t are edges adjacent to f and sp and  

w2t+1,….., w3t are edges adjacent to s and fp. 

Now, d = min (4t + 4, 6t) 

     = 4t + 4 

Then h : V (G) → {1, 3,…., 8t + 9} and  

k : E (G) → {2, 4,…., 8t + 8} are assigned as 

h (sp) = 6t – 4p + 7, p = 1 to t 

h (s) = 1 

h (f) = 3 

h (fp) = 2p + 3,  p = 1 to t 

𝑘 (𝑤𝑞) = {

7𝑡 − 4𝑞 + 2;                𝑓𝑜𝑟 𝑞 = 1 𝑡𝑜 𝑡
10t − 4q + 4 ;  𝑓𝑜𝑟 q =  t + 1  𝑡𝑜 2t
2q − 4t + 2 ;  𝑓𝑜𝑟 q =  2t + 1 𝑡𝑜 3t

 

The above labeling construction satisfies h (fp) ≡ h (s)(mod k (w q)) for every edge of G.  

Hence, spliting graph of a star graph is odd-even congruence graph. 

Example 3.6 

Consider the graph G = Spl (St) with t = 8 

3 

 

 

 

 

51 23 

 

 

 

 

 

 

5 7 9 11 13 15 17 19 

Figure - 4 - Spl (S8) 

The given G = Spl (S8) admits odd-even congruence labeling and it depicts in figure – 4 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

146 
https://internationalpubls.com 

    

Theorem 3.7 

The graph acquired by connecting two copies of even cycle Cr by Pn is odd-even congruence graph. 

Proof: 

Suppose G is acquired by connecting two copies of even cycle Cr by Pt, with 

 |V | = 2r + t − 2 and |E| = 2r + t − 1 edges. 

Let s1, s2, ...sr, sr+1, sr+2,…, s2r+t−3, s2r+t−2 be the vertices of G. 

The path s1 to s2r+t−2 form a spanning path in G. 

The vertex sm and s[r+(t−2])+1 are the common vertex of the first and second Cr & Pt respectively. 

d = min (2 (2r + t − 2), 2 (2r + t − 1)) 

= 2 (2r + t − 2) 

Define  h : V (G) → {1, 3,…,(8r + 4t − 4)} as following 

for 1 ≤ p ≤ r − 1 

  ℎ(𝑠𝑝) = {
𝑝               ; 𝑝 𝑖𝑠 𝑜𝑑𝑑

𝑑 + 7 − 𝑝; 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛
 

for r ≤ p ≤ (3r)/2+t-1 

ℎ(𝑠𝑝) = {
𝑑 + 8 − 𝑝  ; 𝑝 𝑖𝑠 𝑜𝑑𝑑

𝑝 + 1           ; 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛
 

for (3r)/2+t ≤ p ≤ 2r+t-2 

ℎ(𝑠𝑝) = {
𝑑 + 6 − 𝑝 ; 𝑝 𝑖𝑠 𝑜𝑑𝑑
𝑝 + 3        ; 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛

 

then the edges of G are labeled as 

k (wp) = | h (sp) − h (sq) | 

Obviously, h(sp) satisfies modulo division by k (wp). 

Thus, the graph acquired by connecting two copies of even cycle Cr by a path Pt is odd-even 

congruence graph. 

Example 3.8 

Let G be a graph acquired by connecting two copies of even cycle C10 by a path P5 

 

 

 

 

 

 

 

 

 

 

 

Figure - 5 

Figure - 5 reveals that the graph acquired by connecting two copies of even cycle C10 by a path P5 is 

an odd-even congruence graph 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

147 
https://internationalpubls.com 

Theorem 3.9 

 K1,t ⊗ P2 is odd-even congruence graph. 

Proof: 

The tensor product of star graph K1,t and path P2 is denoted as G = K1,t ⊗ P2 with  

|V | = 2t + 2 and |E| = 2t.  

Let s1, s2,…..st+1 are vertex set of K1,t , s1 is apex vertex and 

 f1,  f2 is vertex set of P2. 

V (G) = (s1, f1),(s2, f1), ......, (st+1, f1),(s1, f2),(s2, f2), ....... , (st+1, f2) 

E (G) = e1, e2, ....., et, et+1, ..... , e2t 

where, 

w1, w2, ....... , wn are the edges adjacent with the vertex (sp, f1) and 

wt+1, wt+2, ........ , w2t are the edges adjacent with the vertex (sq, f2) 

d = min (2 (2t + 2), 2 (2t)) 

 = 4t 

Label the vertices h : V (G) → {1, 3, ......8t + 1} and edges k : E (G) → {2, 4,….,8t} are labeled in the 

following way 

h (sp, f1) = 2p − 1 for 1 ≤ p ≤ t + 1 

h (sq, f2) = 2 (t + q) + 1 for 1 ≤ q ≤ t + 1 

  𝑘(𝑤𝑝) =  {
3𝑡 + 2(𝑝 − 1)         ; 𝑓𝑜𝑟 𝑝 = 1 𝑡𝑜 𝑡
4𝑡 − 2𝑝 + 2  ; 𝑓𝑜𝑟 𝑝 = 𝑡 + 1 𝑡𝑜 2𝑡

 

Evidently, 2 (t + q) + 1 – 2p + 1 ≡ (mod (3t + 2p − 2)) 

i.e, (3t + 2p − 2) divides (2 (t + q) – 2p + 2) 

Hence, K1,t ⊗ P2 was an odd-even congruence graph. 

Example 3.10 

Let G = K1,4 ⊗ P2, t = 4 

1 3 5 7 9 

11 13 15 17 19 

 

 

Figure - 6 K1,4 ⊗ P2 

Figure - 6 represents the odd-even congruence labeling of K1,4 ⊗ P2 

Theorem 3.11 

The graph D2 (Pt) is odd-even congruence graph. 

Proof: 

Suppose G = D2 (Pt) is the shadow graph of the path Pt with |V | = 2t and |E| = 4 (t − 1). 

Let s1, s2, ....st be the vertices of first Pt and f1, f2,….,ft are vertices of second path Pt. 

Here, d = min (2 (2t), 2 (4 (t − 1))) 

   

12 

 
14 16 

18 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

148 
https://internationalpubls.com 

  = 4t 

The vertices h : V (G) → {1, 3, ......8t + 1} and edges k : E (G) → {2, 4,……8t} are labeled as given 

below 

  ℎ(𝑠𝑝) = {
4𝑝 − 3          ; 𝑝 𝑖𝑠 𝑜𝑑𝑑

8𝑡 − 4𝑝 + 1 ; 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛
 

  ℎ(𝑓𝑝) = {
4𝑝 − 1          ; 𝑝 𝑖𝑠 𝑜𝑑𝑑

8𝑡 − 4𝑝 − 3 ; 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛
 

 The edge wp = sf are labeled as follows 

k (wp) = | h (s) − h (f)| 

Apparently, the vertex label satisfies modulo division by its corresponding edge label. Hence D2 (Pt) 

is odd-even congruence graph. 

Example 3.12 

Suppose G = D2 (P6) with t = 6 

 
Figure - 7 D2 (P6) 

Odd-even congruence labeling of the shadow graph D2 (P6) is exposed in figure – 7 

4. Conclusion 

Labeling in graph theory has paid more attention for many researchers. New concept of labeling such 

as odd-even congruence labeling based on modulo division has been defined. This paper examines the 

existence of odd-even congruence labeling for complete bipartite graph, Comb graph, spliting graph 

of a star graph and graph acquired by connecting two copies of even cycle Cr by a path Pt were proved. 

Also, it is proved that K1,t ⊗ P2 and D2 (Pt) admits odd-even congruence labeling. The odd-even 

congruence labeling is open to investigate for some other family of graphs and can be applied in 

communication networks to gaurd the informations. 

References 

[1] Bondy J A and Murty U S R, Springer International Edition (2008). 

[2] Gallian JA, The eletronic journal of combinatorices, 18 DS6 (2011). 

[3] Harary F, Addison-Wesley, Reading, Mass (1969). 

[4] Ebin Raja Merly E and Anto A M, International Journal of Emerging Technologies in 

Engineering Research, 4(10) (2016). 

[5] Ganesan V and Lavanya S, IOSR Journal of Mathematics, 15(6), 04–06 (2019). 

[6] Weisstein Eric W, Mathworld. 

[7] Satyanarayana Bhavanari, Srinivasula Devanaboina and Mallikarjun Bhavanari, Research Journal 

of Science & IT Management RJSITM, 5 (2016). 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 1 (2024) 

 

 

149 
https://internationalpubls.com 

[8] Rosa A, Graph Theory: Int Symp., 349–355(1966). 

[9] Lakshmi Prasanna N, Sravanthi K and Nagalla Sundhakar, Oriental Journal of Computer Science & 

Technology, 7(1), 139-145 (2014). 

[10] Sridevi S, Navaneethakrishnan S, Nagarajan A and Nagarajan K, Journal of Applied Mathematics 

& Informat- ics, 30, 913–923 (2012). 

[11] Sirous Moradi, Iranian Journal of Mathematical Sciences and Informatics, 7(1), 73–81 (2012). 

[12] Jayasekaran C and Little Flower J, International Journal of Pure and Applied Mathematics, 

120(3), 303–313 (2018). 

[13] Kanakambika K and Thamizhendhi G, Journal of Xidian University, 14(4), 3551–3565 (2020). 

[14] Kanakambika K and Thamizhendhi G, IGI Global (2022).