Published: 01 January 2025

A novel problem and algorithm for solving permuted cordial labeling of corona product between two graphs

Khalid A. Alsatami1
Yasmin Algrawani2
Atef Abd El-hay3
1Department of Mathematics, College of Science, Qassim University, Buraydah, Kingdom of Saudi Arabia
2Department of Basic Sciences, Modern Academy for Engineering and Technology, Cairo, Egypt
3Mathematics and Computer Science Department, Faculty of Science Menoufia University, Menoufia, Egypt
Corresponding Author:
Atef Abd El-hay
Article in Press
Views 27
Reads 13
Downloads 78

Abstract

This study has come up with a new application of permuted cordial labeling initiated by two graphs based on their corona product, furthering the cause of a better comprehension of and research into specific types of graphs. The Permuted cordial labeling construction for the corona product of graphs consisting of paths, cycles, second power of a path and second power of cycle graphs may facilitate the consideration of the properties and structures of the graphs. It helps us to study its topological properties, connectivity images, symmetries and other properties.

1. Introduction

Graph theory is widely known to have applications in many other academic fields, including communication, physics, chemistry, biology, computer science, psychology, sociology, and economics [1, 2]. One area of graph theory that has received a lot of recent development is graph labelling. Labeled graphs are useful models for many fields, including as coding theory, circuit design, radar, X-ray crystallography, and database management [3].

A particular kind of graph labeling involves assigning values from an established set to its vertices, assigning an automatically induced label to its edges, and ensuring that the labeling satisfies certain conditions. On this subject, the paper by Gallian [4] is an excellent resource. Two of the most important categories are labeling that is graceful and harmonic. In 1966 and 1972, respectively, Rosa [5] and Golomb [6] separately developed graceful labeling, and in 1980, Graham and Sloane [7] concluded the first investigation on harmonic labeling.

A third important type of labeling that Cahit [8] developed in 1990 and which combines components of the other two is cordial labeling. Cordial labelings use labels 0 and 1, together with the induced label (f(v)+f(w))(mod2), which naturally equals |f(v)-f(w)|, in contrast to graceful and harmonious labelings, which use labels |f(v)-f(w)| and f(v)+f(w) (modulo the number of edges), respectively. Since mathematics modulo 2 is an essential part of computer science, cordial labeling has a lot in common with that field. In [9] A. Abd El-hay and et.al, prove the corona product of paths and third power of lemniscate graph PkLn,m3 are signed product-cordial for all k, n and m. In [10] ELrokh and et.al, proved that each path, cycle and Fan admits permuted cordial labeling. The Wheel graph Wn, n3 admits permuted cordial labeling except n2mod3 and n even. Moreover, they proved that the union of PnPm, n, m2 admits a permuted cordial labeling for all n,m. The union of CnCm, n, m3 admits a permuted cordial labeling for all n, m. The union of PnCm, n2, m3 admits a permuted cordial labeling for all n, m. For more details about other labeling that are related to cordial labeling such as permuted logically, total cordial, signed product cordial, etc. the reader is referred to [10-17].

The rest of this paper is structured as follows: permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles are presented in Section 3. Section 4 proposes an algorithm for determining the permuted cordial labeling of a given graph. Section 5 investigate the discussion on Permuted Cordial Labeling and Its Engineering Applications. Finally, in Section 6, conclusions are drawn.

2. Materials and methods

We can use these code of labeling as follows.

Table 1Labeling methods

D3r
gfi. gfi repeated r time
W3k
gfi. gfi repeated k time
W3r
fgi. fgi repeated r time
E3k
fgi. fgi repeated k time
M3r
igf.igf repeated r time
M3k
igf.igf repeated k time
E3r
gif.gif repeated r time
D3k
gif.gif repeated k time
P3r
ifg.ifg repeated r time
S3k
ifg.ifg repeated k time
S3r
fig.fig repeated r time
P3k
fig.fig repeated k time

Sometimes, we modify D3r, W3r, and M3r by adding symbols at one end or the other or both; for example, M3rgI means the labeling Igf...Igf(r-times)gi. Similarly, M3rf means the labeling Igf...Igf(r-time)f. v(I), v(g), and v(f) represent the number of vertices labeled I, g, and f, respectively. Similarly, we denoted e(i), e(g), and e(f) to be the number of edges labeled I, g, and f, respectively, for the graph G.

A vertex labeling of graph G of h:V{I,g,f} with induced edge labeling h*:E(G){I,g,f} defined by:

1
v(i)v(f)v(g)u(i)Ifgu(f)fgIu(g)gIf

is called permuted cordial labeling if vx-vy1 and ex-ey1, xy and x,yI,f,g where vx (respectively, ex) is the number of vertices (respectively, edges) labeled with xI,f,g. A graph G is permuted cordial if it admits a permuted labeling. For a given labeling of the corona GH, we denote v(j) and e(j) (j=I,f,g) to represent the numbers of vertices and edges labeled by j, respectively. We denote xj and aj to be the numbers of vertices and edges labeled by I,f,g, respectively, for the graph G. Also, we let yj, yi' and bj, bi' be those for H, which are connected to the vertices labeled j of G. It is easy to verify that:

2
vi=xi+xiyi+xfy'i+xgy''i,vf=xf+xiyf+xfy'f+xgy''f,vg=xg+xiyg+xfy'g+xgy''g,ei=ai+xibi+xfb'i+xgb''i+ xiyi+xfy'g+xgy''f,ef=af+xibf+xfb'f+xgb''f+ xiyf+xfy'i+xgy''g,eg=ag+xibg+xfb'g+xgb''g+ xiyg+xfy'f+xgy''i.

Finally, for particular labeling A and B that are used for G1 and G2 , respectively, we let [A;B] denote the labeling for the corona of G1 and G2. Section one contains a brief literary analysis of the topic of this work. Section Two deals with the Materials and Methods employed throughout. Whereas section three is devoted to studying the permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles. Section four proposes an algorithm for determining the permuted cordiality of a given graph. Section five investigated the discussion on Permuted Cordial Labeling and Its Engineering Applications. The last section is the conclusion which summarizes the important points of our finding in this paper.

3. Results

In this section we shall prove that the permuted cordial labeling for the corona product of paths, cycles, second power of paths, and second power of cycles.

Theorem 1. PnPm is permuted cordial for all n1 and m1.

Proof. Let n=3r+i' (i'=0,1,2 and r0), and m=3k+j (j=0,1,2 and k2), then, we may use the labeling Ai' or Aj' for Pn as given in Table 2. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Pm, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm which are connected to the vertices labeled I in Pn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm which are connected to the vertices labeled 𝑓 in Pm as given in Table 3. Using Table 4 and the Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 4. Since all of these values are 1 or 0, the theorem follows.

Table 2Labeling of Pn

n=3r+i
Pn
xi
xf
xg
ai
af
ag
i=0
A0=D3r
r
r
r
r
r
r-1
i=1
A1=D3rg
r
r
r+1
r
r
r
i=1
A'1=W3rf
r
r+1
r
r
r
r
i=1
A''1=M3ri
r+1
r
r
r
r
r
i=2
A2=E3rgi
r+1
r
r+1
r
r
r+1
i=2
A'2=S3rgf
r+1
r
r+1
r+1
r
r
i=2
A''2=D3rig
r+1
r
r+1
r+1
r
r

Table 3Labeling of Pm

m=3k+j
Pm
yi
yf
yg
bi
bf
bg
i=0
B0=M3k
k
k
k
k
k-1
k
i=0
B'0=D3k
k
k
k
k-1
k
k
i=0
B''0=W3k
k
k
k
k
k
k-1
i=0
C0=D3k
k
k
k
k-1
k
k
i=0
C'0=M3k
k
k
k
k
k-1
k
i=0
C''0=W3k
k
k
k
k
k
k-1
i=1
B1=M3ki
k+1
k
k
k
k
k
i=1
B'1=P3kf
k
k+1
k
k
k
k
i=1
B''1=W3kg
k
k
k+1
k
k
k
i=1
C1=E3kf
k
k+1
k
k
k
k
i=1
C'1=D3kg
k
k
k+1
k
k
k
i=1
C''1=S3ki
k+1
k
k
k
k
k
i=2
B2=M3kfi
k+1
k+1
k
k
k
k+1
i=2
B'2=S3kgi
k+1
k
k+1
k
k+1
k
i=2
B''2=S3kgi
k+1
k
k+1
k
k+1
k
i=2
C2=W3kgf
k
k+1
k+1
k+1
k
k
i=2
C'2=D3kgi
k+1
k
k+1
k
k
k+1
i=2
C''2=M3kif
k+1
k+1
k
k
k+1
k
i=2
D2=W3kgf
k+1
k+1
k
k
k
k+1
i=2
D'2=D3kgi
k
k+1
k+1
k+1
k
k
i=2
D''2=M3kif
k+1
k
k+1
k
k+1
k

Table 4Labeling of Pn⊙Pm

n=3r+i
m=3r+j
Pn
Pm
|v(x)-v(y)|,
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B''0,B'0,B0,
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
B''0,B'0,B0,,B''0
0, 0, 0
0, 0, 0
i=1
j=1
A'1
C'1,C''1,C1,,C'1
1, 1, 0
1, 1, 0
i=1
j=2
A''1
C2,C''2,C'2,,C2
1, 1, 0
1, 1, 0
i=2
j=0
A2
C''0,C0,C'0,,C''0,C0
0, 0, 0
0, 0, 0
i=2
j=1
A'2
C'1,C1,C''1,,C''1C'1
1, 1, 0
0, 0, 0
i=2
j=2
A''2
D''2,D'2,D2,,D2,D''2
1, 1, 0
1, 1, 0

Theorem 2. CnCm is permuted cordial for all n3 and m3 except at n=2(mode3) with m=2(mode3).

Proof. Let n=3r+i' (i'=0,1,2 and r1), and m=3k+j (j=0,1,2 and k1), then, we may use the labeling Ai' or Aj' for Cn as given in Table 5. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Cm, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm which are connected to the vertices labeled I in Cn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm which are connected to the vertices labeled 𝑓 in Cm as given in Table 6. Using Table 7 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 7. Since all of these values are 1 or 0, the theorem follows.

Table 5Labeling of Cn

n=3r+i
Cn
xi
xf
xg
ai
af
ag
i=0
A0=W3r
r
r
r
r
r
r
i=1
A1=P3ri
r+1
r
r
r+1
r
r
i=2
A2=P3rgf
r
r+1
r+1
r
r+1
r+1
i=2
A'2=W3rig
r+1
r
r+1
r+1
r+1
r
i=2
A"2=D3rgi
r+1
r
r+1
r
r
r+2

Table 6Labeling of Cm

m=3k+j
Cm
yi
yf
yg
bi
bf
bg
i=0
B0=W3k
k
k
k
k
k
k
i=0
B'0=W3k
k
k
k
k
k
k
i=0
B''0=W3k
k
k
k
k
k
k
i=1
B1=iP3k
k+1
k
k
k-1
k+1
k+1
i=1
B'1=gW3k
k
k
k+1
k
k+1
k
i=1
B''1=fP3k
k
k+1
k
k
k
k+1
i=1
C1=fP3k
k
k+1
k
k
k
k+1
i=1
C'1=gW3k
k
k
k+1
k
k+1
k
i=1
C''1=iP3k
k+1
k
k
k+
k
k
i=2
B2=ifE3k
k+1
k
k+1
k+1
k+1
k
i=2
B'2=fgD3k
k
k+1
k+1
k
k+1
k+1
i=2
B''2=igW3k
k+1
k+1
k
k+1
k
k+1
i=2
C2=P3kgf
k
k+1
k+1
k
k+1
k+1
i=2
C'2=gW3ki
k+1
k
k+1
k+1
k+1
k
i=2
C"2=fE3ki
k+1
k+1
k
k+1
k
k+1

Table 7Labeling of Cn⊙Cm

n=3r+i
m=3r+j
Cn
Cm
vx-vy
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B''0,B'0,B0,
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
B0,B'0,B''0,..,B0
0, 0, 0
0, 0, 0
i=1
j=1
A1
C1,C'1,C''1,..,C1
1, 1, 0
1, 1, 0
i=1
j=2
A1
C2,C'2,C''2,..,C2
1, 1, 0
1, 1, 0
i=2
j=0
A2
B'0,B0,B''0,,B''0,B'0
0, 0, 0
0, 0, 0
i=2
j=1
A'2
B''1,B'1,B1,,B1,B''1
1, 1, 0
1, 1, 0

Theorem 3. PnCm is permuted cordial for all n1 and m3.

Proof. Let n=3r+i' (i'=0,1,2 and r0), and m=3k+j (j=0,1,2 and k1), then, we may use the labeling Ai' or Aj' for Pn as given in Table 8. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Cm, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm which are connected to the vertices labeled I in Pn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm which are connected to the vertices labeled 𝑓 in Cm as given in Table 9. Using Table 10 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 10. Since all of these values are 1 or 0, the theorem follows.

Table 8Labeling of Pn

n=3r+i
Pn
xi
xf
xg
ai
af
ag
i=0
A0=D3r
r
r
r
r
r
r-1
i=1
A1=D3rg
r
r
r+1
r
r
r
i=1
A'1=fM3r
r
r+1
r
r
r
r
i=1
A''1=iD3r
r+1
r
r
r
r
r
i=2
A2=D3rgf
r
r+1
r+1
r+1
r
r
i=2
A'2=D3rig
r+1
r
r+1
r+1
r
r
i=2
A"2=D3rgi
r+1
r
r+1
r
r
r+1

Table 9Labeling of Cm

m=3k+j
Cm
yi
yf
yg
bi
bf
bg
i=0
B0=W3k
k
k
k
k
k
k
i=1
B1=fE3k
k
k+1
k
k
k
k+1
i=1
B'1=E3ki
k+1
k
k
k+1
k
k
i=1
B''1=M3kg
k
k
k+1
k+1
k-1
k+1
i=1
C1=iP3k
k+1
k
k
k-1
k+1
k+1
i=1
C'1=W3kg
k
k
k+1
k
k+1
k
i=1
C''1=iP3k
k
k+1
k
k
k
k+1
i=2
B2=ifE3k
k+1
k+1
k
k+1
k
k+1
i=2
B'2=fgD3k
k
k+1
k+1
k
k+1
k+1
i=2
B''2=igW3k
k+1
k
k+1
k+1
k+1
k
i=2
C2=fgP3k
k+1
k
k+1
k
k+1
k+1
i=2
C'2=igW3k
k+1
k+1
k
k+1
k
k+1
i=2
C''2=ifE3k
k
k+1
k+1
k+1
k
k+1

Table 10Labeling of Pn⊙Cm

n=3r+i
m=3k+j
Pn
Cm
vx-vy
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B0,B0,B0,
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
B0,B0,B0,,B0
0, 0, 0
0, 0, 0
i=1
j=1
A'1
C'1,C1,C''1,C'1
1, 1, 0
1, 1, 0
i=1
j=2
A''1
C2,C''2,C'2,,C2
1, 1, 0
1, 1, 0
i=2
j=0
A2
B0,B0,B0,,B0,B0
0, 0, 0
0, 0, 0
i=2
j=1
A'2
C''1,C'1,C1,,C1,C''1
1, 1, 0
1, 1, 0
i=2
j=2
A''2
C''2,C'2,C2,,C''2,C2
1, 1, 0
1, 1, 0

Theorem 4. CnPm is permuted cordial for all n3 and m1.

Proof. Let n=3r+i' (i'=0,1,2 and r1), and m=3k+j (j=0,1,2 and k0), then, we may use the labeling Ai' or Aj' for Cn as given in Table 11. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Cm, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm which are connected to the vertices labeled I in Cn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm which are connected to the vertices labeled 𝑓 in Pm as given in Table 12. Using Table 13 and Eq. (1) and Eq.(2), we can compute the values shown in the last two columns of Table 13. Since all of these values are 1 or 0, the theorem follows.

Table 11Labeling of Cn

n=3r+i
Cn
xi
xf
xg
ai
af
ag
i=0
A0=D3r
r
r
r
r
r
r
i=1
A1=E3rg
r
r
r+1
r
r+1
r
i=1
A'1=D3rg
r
r
r+1
r
r+1
r
i=2
A2=P3rgf
r
r+1
r+1
r+1
r+2
r-1
i=2
A'2=D3rfg
r+1
r
r+1
r+1
r+1
r

Table 12Labeling of Pm

m=3k+j
Pm
yi
yf
yg
bi
bf
bg
i=0
B0=D3k
k
k
k
k-1
k
k
i=0
B'0=M3k
k
k
k
k
k-1
k
i=0
B''0=W3k
k
k
k
k
k
k-1
i=0
C0=E3k
k
k
k
k
k-1
k
i=0
C'0=M3k
k
k
k
k
k
k-1
i=0
C''0=D3k
k
k
k
k-1
k
k
i=0
D0=M3k
k
k
k
k
k-1
k
i=0
D'0=D3k
k
k
k
k-1
k
k
i=0
D''0=W3k
k
k
k
k
k
k-1
i=1
B1=M3ki
k+1
k
k
k
k
k
i=1
B'1=E3kf
k
k+1
k
k
k
k
i=1
B''1=W3kg
k
k
k+1
k
k
k
i=1
C1=P3kf
k
k+1
k
k
k
k
i=1
C'1=W3kg
k
k
k+1
k
k
k
i=1
C''1=S3ki
k+1
k
k
k
k
k
i=1
D1=W3kg
k
k
k+1
k
k
k
i=1
D'1=P3kf
k
k+1
k
k
k
k
i=1
D''1=iS3k
k+1
k
k
k+1
k+1
k-1
i=2
B2=P3kif
k+1
k+1
k
k-1
k+1
k+1
i=2
B'2=M3kig
k+1
k
k+1
k
k
k+1
i=2
B''2=E3kgf
k
k+1
k+1
k+1
k-1
k+1
i=2
C2=igW3k
k+1
k
k+1
k
k+1
k
i=2
C'2=P3kfg
k
k+1
k+1
k+1
k
k
i=2
C''2=E3kfi
k+1
k+1
k
k
k+1
k
i=2
D2=M3kfi
k+1
k+1
k
k
k
k+1
i=2
D'2=S3kig
k+1
k
k+1
k
k
k+1
i=2
D''2=D3kfg
k
k+1
k+1
k
k
k+1

Table 13Labeling of Cn⊙Pm

n=3r+i
m=3r+j
Cn
Pm
vx-vy
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B''0,B'0,B0,
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
D''0,D0,D'0,..,D''0
0, 0, 0
0, 0, 0
i=1
j=1
A'1
C''1,C'1,C1,,C''1
1, 1, 0
1, 1, 0
i=1
j=2
A'1
C''2,C'2,C2,..,C''2
1, 1, 0
1, 1, 0
i=2
j=0
A2
D0,D'0,D''0,,D''0D'0
0, 0, 0
0, 0, 0
i=2
j=1
A2
D''1,D'1,D1,,D'1,D''1
1, 1, 0
1, 1, 0
i=2
j=2
A'2
D2,D'2,D''2,,D'2D2
1, 1, 0
1, 1, 0

Theorem 5. PnPm2 is permuted cordial for all n1 and m1.

Proof. Let n=3r+i' (i'=0,1,2 and r0), and m=3k+j (j=0,1,2 and k2), then, we may use the labeling Ai' or Aj' for Pn as given in Table 14. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Pm2, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm2 which are connected to the vertices labeled I in Pn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Pm2 which are connected to the vertices labeled 𝑓 in Pm2 as given in Table 15. Using Table 16 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 16. Since all of these values are 1 or 0, the theorem follows.

Table 14Labeling of Pn

n=3r+i
Pn
xi
xf
xg
ai
af
ag
i=0
A0=D3r
r
r
r
r
r
r-1
i=1
A1=D3rg
r
r
r+1
r
r
r
i=2
A2=D3rgf
r
r+1
r+1
r+1
r
r
i=2
A'2=fgE3r
r
r+1
r+1
r
r+1
r
i=2
A''2=ifW3r
r+1
r+1
r
r
r
r+1

Table 15Labeling of P2m

m=3k+j
P2m
yi
yf
yg
bi
bf
bg
i=0
B0=E3k
k
k
k
2k-1
2k-1
2k-1
i=0
B'0=P3k
k
k
k
2k-1
2k-1
2k-1
i=0
B''0=W3k
k
k
k
2k-1
2k-1
2k-1
i=1
B1=M3kf
k
k+1
k
2k
2k-1
2k
i=1
B'1=M3kg
k
k
k+1
2k
2k
2k-1
i=1
B''1=iE3k
k+1
k
k
2k-1
2k
2k
i=1
C1=M3kf
k
k+1
k
2k
2k-1
2k
i=1
C'1=iE3k
k
k
k+1
2k-1
2k
2k
i=1
C''1=iS3k
k+1
k
k
2k
2k
2k-1
i=1
D1=M3kg
k
k
k+1
2k
2k
2k-1
i=1
D'1=P3kf
k
k+1
k
2k
2k
2k-1
i=1
D''1=iS3k
k+1
k
k
2k
2k
2k-1
i=2
B2=D3kfg
k
k+1
k+1
2k+1
2k
2k
i=2
B'2=igE3k
k+1
k
k+1
2k
2k+1
2k
i=2
B''2=ifW3k
k+1
k+1
k
2k
2k
2k+1
i=2
C2=D3kfg
k
k+1
k+1
2k+1
2k
2k
i=2
C'2=M3kig
k+1
k
k+1
2k
2k
2k+1
i=2
C''2=M3kfi
k+1
k+1
k
2k
2k+1
2k
i=2
D2=E3kgf
k+1
k
k+1
2k
2k+1
2k
i=2
D'2=M3kfi
k
k+1
k+1
2k
2k+1
2k
i=2
D''2=igE3k
k+1
k+1
k
2k
2k+1
2k

Table 16Labeling of Pn⊙P2m

n=3r+i
m=3r+j
Pn
P2m
vx-vy
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B''0,B'0,B0,
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
B''0,B'0,B0,..,B''0
0, 0, 0
0, 0, 0
i=1
j=1
A1
C''1,C'1,C1,..,C''1
1, 1, 0
1, 1, 0
i=1
j=2
A1
C''2,C'2,C2,..,C''2
1, 1, 0
1, 1, 0
i=2
j=0
A2
B''0,B'0,B0,,B''0,B'0
0, 0, 0
0, 0, 0
i=2
j=1
A'2
D'1,D''1, D''1,D1,D'1,
1, 1, 0
1, 1, 0
i=2
j=2
A''2
D2,D'2, D'2,D''2,D2,
1, 1, 0
1, 1, 0

Theorem 6. PnCm2 is permuted cordial for all n1 and m3.

Proof. Let n=3r+i' (i'=0,1,2 and r0), and m=3k+j (j=0,1,2 and k1), then, we may use the labeling Ai' or Aj' for Pn as given in Table 17. For a given value of j with 0i', j2, we may use one of the labeling in the set {Bi,Bi',B''i,Ci,Ci',C''i} for Cm2, where Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm2 which are connected to the vertices labeled I in Pn, while Bi, Bi', B''i, Ci, Ci' and C''i are the labeling of Cm2 which are connected to the vertices labeled 𝑓 in Cm2 as given in Table 18. Using Table 19 and Eq. (1) and Eq. (2), we can compute the values shown in the last two columns of Table 19. Since all of these values are 1 or 0, the theorem follows.

Table 17Labeling of Pn

n=3r+i
Pn
xi
xf
xg
ai
af
ag
i=0
A0=D3r
r
r
r
r
r
r-1
i=1
A1=D3rg
r
r
r+1
r
r
r
i=2
A2=P3rgf
r
r+1
r+1
r
r+1
r

Table 18Labeling of C2m

m=3k+j
C2m
yi
yf
yg
bi
bf
bg
i=0
B0=E3k
k
k
k
2k-1
2k
2k-1
i=0
B'0=P3k
k
k
k
2k
2k-1
2k-1
i=0
B''0=W3k
k
k
k
2k-1
2k-1
2k
i=0
C0=D3k
k
k
k
2k
2k-1
2k-1
i=0
C'0=E3k
k
k
k
2k-1
2k
2k-1
i=0
C''0=S3k
k
k
k
2k-1
2k-1
2k
i=1
B1=W3kf
k
k+1
k
2k
2k
2k
i=1
B'1=E3kg
k
k
k+1
2k
2k
2k
i=1
B''1=S3ki
k+1
k
k
2k
2k
2k
i=2
B2=S3kfi
k
k+1
k+1
2k+1
2k+1
2k
i=2
B'2=S3kgi
k+1
k
k+1
2k+1
2k
2k+1
i=2
B''2=D3kfg
k+1
k+1
k
2k
2k+1
2k+1
i=2
C2=D3kfg
k
k+1
k+1
2k+1
2k
2k
i=2
C'2=S3kgi
k+1
k
k+1
2k+1
2k
2k+1
i=2
C''2=S3kfi
k+1
k+1
k
2k
2k+1
2k+1
i=2
D2=S3kgi
k
k+1
k+1
2k+1
2k+1
2k
i=2
D'2=S3kfi
k+1
k
k+1
2k+1
2k
2k+1
i=2
D''2=D3kfg
k+1
k+1
k
2k
2k+1
2k+1

Table 19Labeling of Pn⊙C2m

n=3r+i
m=3r+j
Pn
C2m
vx-vy
xy,
x,y{i,f,g}
|e(x)-e(y)|
xy,
x,y{i,f,g}
i=0
j=0
A0
B''0,B'0,B0
0, 0, 0
0, 0, 0
i=0
j=1
A0
B''1,B'1,B1,
1, 1, 0
1, 1, 0
i=0
j=2
A0
B''2,B'2,B2,
1, 1, 0
1, 1, 0
i=1
j=0
A1
C''0,C'0,C0,..,C''0
0, 0, 0
0, 0, 0
i=1
j=1
A1
B''1,B'1,B1,..,B''1
1, 1, 0
1, 1, 0
i=1
j=2
A1
B''2,B'2,B2,..,B''2
1, 1, 0
1, 1, 0
i=2
j=0
A2
B'0,B0,B''0,,B''0,B'0
0, 0, 0
0, 0, 0
i=2
j=1
A2
B'1,B1,B''1,,B''1,B'1
1, 1, 0
1, 1, 0
i=2
j=2
A2
B'2,B2,B''2,,B''2,B'2
1, 1, 0
1, 1, 0

4. Algorithm

In this section, we propose an algorithm for calculating the permuted cordial labeling for any graph 𝐺. This algorithm provides a framework for attempting to find a permuted cordial labeling for a given graph. It’s important to note that not all graphs will admit a permuted cordial labeling, and the specific method of assigning labels to vertices in step 3 can vary based on the graph’s structure and properties. we assume that labeling each vertex and edge takes constant time, then the time complexity of Algorithm 1 is 𝑂(𝑛), since each vertex and edge is visited once.

Table 20Algorithm for Permuted cordial labeling of a graph

Algorithm1: Permuted Cordial Labeling of a Graph
Input:A graph GV,E
Output:A Permuted cordial labeling of G if it exists
Begin
Step 1. Initialize three counters, vI, vf and vg, to 0.
Step 2. Initialize three counters, eI, ef and eg, to 0.
Step 3. For each vertex v in V:
a. Assign a label fvI,f,g to the vertex v.
b. If fv==I, increment vI; else If fv==f, increment vf; else increment vg.
Step 4. For each edge eu,v in E:
a. Assign a label fe=fu o fv to the edge e.
b. If fe==I, increment eI; If fe==f, increment ef; else increment eg.
Step 5. Check the Permuted cordial condition:
a. If vx-vy1 and ex-ey1, xy and x, y{i,f,g}:
i. The labeling is cordial.
ii. Output the labeling of vertices and edges.
b. Else:
i. The graph G does not admit a Permuted cordial labeling.
ii. Output that no Permuted cordial labeling exists.
End Algorithm

5. Discussion

In graph theory, permuted cordial labeling is an intriguing idea with possible applications in a number of industrial domains. A graph's vertices are given labels using this labeling technique so that the total of the labels of nearby vertices satisfies predetermined requirements. In engineering applications, this idea can be useful in the following ways:

5.1. Network design and optimization

In telecommunications and computer networks, it is important for the efficient routing of data. Permuted cordial labeling can be a means of optimization for network topologies that can minimize the number of connections among them while still having robust communication paths. Applying this labeling, engineers are able to design networks with load balancing and low latency which in turn results in a better performance.

5.2. Resource allocation

In systems, wherein resources, such as bandwidth or power, must be allocated, the permuted cordial labeling becomes a just and effective model of distribution. E.g. In a wireless sensor network, this labeling will be a great deal in the arrangement of the sensor nodes in the way of having maximum coverage and minimum energy consumption.

6. Conclusions

We proved that each PnPm, n, m2 admits permuted cordial labeling. Each CnCm, n, m3 admits permuted cordial labeling for all n, m(1mod3;2mod3). Each PnCm, n1, m3 admits a permuted cordial labeling. CnPm, n3, m1 admits permuted cordial labeling.

Moreover, we proved that the corona of PnP2m, n, m2 admits a permuted cordial labeling. Also, we proved the corona of PnC2m, n2, m>4 admits a permuted cordial labeling. We proposed an algorithm for determining the Permuted cordial of a given graph. In the future, we will apply permuted cordial labeling to other types of graphs.

References

  • A. Krishnaa, “Some applications of labelled graphs,” International Journal of Mathematics Trends and Technology, Vol. 37, No. 3, pp. 209–213, Sep. 2016, https://doi.org/10.14445/22315373/ijmtt-v37p528
  • D. Narsingh, Graph Theoty with Application to Engineering and Computer Science. New Delhi, India: PrenticeHall of India Pvt., 2003.
  • N. Hartsfield and G. Ringel, Pearls in Graph Theory: a Comprehensive Introduction. Boston, USA: Academic Prress Inc., 1990.
  • J. A. Gallian, “A dynamic survey of graph labeling,” The Electronic Journal of Combinatorics, Vol. 1000, Dec. 2022, https://doi.org/10.37236/11668
  • A. Rosa, “On certain valuations of the vertices of a graph,” in Theory of Graphs, 1967.
  • S. W. Golomb, “How to number a graph in graph theory and computing,” in Graph Theory and Computing, pp. 23–37, Jan. 1972, https://doi.org/10.1016/b978-1-4832-3187-7.50008-8
  • R. L. Graham and N. J. A. Sloane, “On additive bases and harmonious graphs,” SIAM Journal on Algebraic Discrete Methods, Vol. 1, No. 4, pp. 382–404, Dec. 1980, https://doi.org/10.1137/0601045
  • I. Cahit, “On cordial and 3-equitable labeling of graphs,” Utilitas Mathematica, Vol. 37, pp. 189–198, 1990.
  • A. Abd El-Hay, Y. Elmshtaye, and A. Elrokh, “Solving singed product cordial labeling of corona products of paths and the third power of lemniscate graphs,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 14, No. 2, pp. 806–823, 2023, https://doi.org/10.17762/turcomat.v14i2.13737
  • A. Elrokh, M. M. A. Al-Shamiri, M. M. A. Almazah, and A. A. El-Hay, “A novel problem for solving permuted cordial labeling of graphs,” Symmetry, Vol. 15, No. 4, p. 825, Mar. 2023, https://doi.org/10.3390/sym15040825
  • A. Elrokh, Y. Elmshtaye, and A. Abd El-Hay, “The cordiality of cone and lemniscate graphs,” Applied Mathematics and Information Sciences, Vol. 16, No. 6, pp. 1027–1034, Nov. 2022, https://doi.org/10.18576/amis/160620
  • S. Nada, A. Elrokh, and A. Abd El-Hay, “On signed product cordial of lemniscate graph and its second power,” Turkish Journal of Computer and Mathematics Education, Vol. 13, No. 3, pp. 905–913, 2022, https://doi.org/10.17762/turcomat.v13i03.13186
  • Atef Abd El-Hay and A. Elrokh, “Total cordial labeling of corona product of paths and second power of fan graph,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 681–690, 2022, https://doi.org/10.17762/turcomat.v13i03.13097
  • A. Elrokh, M. M. A. Al-Shamiri, and A. Abd El-Hay, “A novel radio geometric mean algorithm for a graph,” Symmetry, Vol. 15, No. 3, p. 570, Feb. 2023, https://doi.org/10.3390/sym15030570
  • S. Nada, A. Elrokh, and Atef Abd El-Hay, “On singed product cordial of cone graph and its second power.,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 597–606, 2022, https://doi.org/10.17762/turcomat.v13i03.13070
  • A. Elrokh, M. A. Al-Shamiri, and A. Abd El-Hay, “A novel problem for solving cordial labeling of corona product between path and third order of cone graphs,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), Vol. 13, No. 3, pp. 970–986, 2022, https://doi.org/10.17762/turcomat.v13i03.13219
  • A. Abd El-Hay and A. Rabie, “Signed product cordial labeling of corona product between paths and second power of fan graphs,” Italian Journal of Pure and Applied Mathematics, Vol. 48, pp. 287–294, 2022.

About this article

Received
11 October 2024
Accepted
19 November 2024
Published
01 January 2025
Keywords
graph theory
labeling
machine learning
algorithms
network security
problem-solving
Acknowledgements

The authors extend their appreciation to Prof. Khalid A. Alsatami, Department of Mathematics, College of Science, Qassim University, Buraydah, KSA for supporting this work. The Researchers would like to thank the Deanship of Graduate Studies and Scientific Research at Qassim University for financial support (QU-APC-2024-9/1).

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

Author Contributions

Khalid A. Alsatami: conceptualization, validation, data curation. Yasmin Algrawani: methodology, formal analysis, supervision. Atef Abd El-hay: software, investigation, resources, visualization, supervision.

Conflict of interest

The authors declare that they have no conflict of interest.