# A Novel Problem to Solve the Logically Labeling of Corona between Paths and Cycles

Authors: Ashraf ELrokh; Mohammed M. Ali Al-Shamiri; Atef Abd El-hay
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this study, we propose a new kind of graph labeling which we call logic labeling and investigate the logically labeling of the corona between pathsPn and cycles Cn, namely, Pn⊙Cm. A graph is said to be logical labeling if it has a 0−1 labeling that satisfies certain properties. The corona G1⊙G2 of two graphs G1 (with n1 vertices and m1 edges) and G2 (with n2 vertices and m2 edges) is defined as the graph formed by taking one copy of G1 and n1 copies of G2 and then connecting the ith vertex of G1 with an edge to every vertex in the ith copy of G2.


---

## Body

## 1. Introduction

Graphs can be used to model a wide range of relationships and processes in physical, biological, social, and information systems. Graphs can also be used to show a wide range of real issues. The term “network” is frequently used to refer to a graph in which attributes are associated with nodes and edges, emphasising its relevance to real-world systems [1].Graphs are used in computer science to illustrate communication networks, data administration, computational devices, and computation flow. A directed graph, for example, can represent a website’s link structure, with the vertices representing web pages and the directed edges representing links from one page to another. Problems in social media, travel, biology, computer chip design, and a variety of other industries can all benefit from a similar approach. As a result, developing algorithms to manage graphs is a major topic in computer science [1, 2]. Graph rewrite systems are usually used to formalise and describe graph transformations. Graph databases, which are designed for transaction—safe, persistent storing and querying of graph—structured data, are a complement to graph transformation systems that focus on rule-based in-memory graph manipulation.Labeling methods are used for a wide range of applications in different subjects including coding theory, computer science, and communication networks. Graph labeling is an assignment of positive integers on vertices or edges or both of them which fulfilled certain conditions. The concept of graph labeling was introduced by Rosa in 1967 [3].The following three properties are shared by the majority of graph labeling problems:(i)
A set of numbers from which to select vertex labels(ii)
A rule that gives each edge a labeling(iii)
Some rules that these labels must meetA Dynamic Survey of Graph Labeling by Gallian [4] is a complete survey of graph labeling. There are several contributions and various types of labeling [1, 3–15]. Graceful labeling and harmonious labeling are two of the major styles of labeling. Graceful labeling is one of the most well-known graph labeling approaches; it was independently developed by Rosa in 1966 [3] and Golomb in 1972 [5], whilst harmonious labeling was initially investigated by Graham and Sloane in 1980 [6]. Cahit proposed a third major style of labeling, cordial, in 1987 [14], which combines elements of the previous two. The cordiality of the corona between cycles Cn and paths Pn was investigated by Nada S. et al. [8]. This research focuses on graph labeling of this type. G is considered to be connected, finite, simple, and undirected throughout.Definition 1.
A binary vertex labeling ofG is a mapping f:V⟶0,1 in which fu is said to be the labeling of u∈V. For an edge e=uv∈E, where u,v∈V, the induced edge labeling f∗:E⟶0,1 is defined by the formula f∗vw=fv+fw+1 (mod 2). Thus, for any edge e, f∗e=1 if its two vertices have the same label and f∗e=0 if they have different labels. Let us denote v0 and v1 be the numbers of vertices labeled by 0 and 1 in V, respectively, and let e0 and e1 be the corresponding numbers of edge in E labeled by 0 and 1, respectively.Definition 2.
Ifv0−v1≤1 and e0−e1≤1 hold, a binary vertex labeling f of G is said to be logical. A graph G is logical if it can be labeled logically. Gallian’s survey [4] is a good starting point for further research on this topic.Definition 3.
The coronaG1⊙G2 of two graphs G1 (with n1 vertices and m1 edges) and G2 (with n2 vertices and m2 edges) is defined as the graph obtained by taking one copy of G1 and n1 copies of G2 and then joining the ith vertex of G1 with an edge to every vertex in the ith copy of G2. According to the definition of the corona, G1⊙G2 has n1+n1n2 vertices and m1+n1m2+n1n2 edges. It is clear that G1⊙G2 is not often isomorphic to G2⊙G1 [7, 9–12].
In this paper, we show thatPn⊙Cm logical labeling if and only if n,m≠1,3mod4.


## 2. Terminology and Notation

Pn denotes a path having n vertices and n−1 edges, while Cn denotes a cycle with n vertices and n edges [9, 10]. Let Mr stand for the labeling 0101⋯01, zero-one repeated r− times if r is even and 0101⋯010 if r is odd; for example, M6=010101 and M5=01010. The labeling 1010⋯10 is denoted by M2r′. We sometimes change the labeling Mr or Mr′ by inserting symbols at one end or the other (or both). L4r denotes the labeling 00110011 … 0011 (repeated r-times) with r≥1 and L4r′ denotes the labeling 11001100 … 1100 (repeated r-times) with r≥1. S4r represents the labeling 10011001 … 1001 (repeated r times) and S¯4r represents the labeling 01100110… 0110 (repeated r times). In most situations, we change this by inserting symbols at one end or the other (or both), so L4r101 represents the labeling 00110011 … 0011101 (repeated r-times) when r≥1 and 101 when r=0. Similarly, 1L4r′ represents the labeling 111001100 … 1100 (repeated r-times) for r≥1 and 1 when r=0. Similarly, 0L4r′1 denotes 011001100 … 11001 when r≥1 and 01 when r=0.For the corona labeling [9], let L;M indicate the special labeling L and M of G⊙H where G is path and H is cycle. The following is an additional notation that we use. For a given labeling of the corona G⊙H, we choose vi and ei (for i=0,1) to be the numbers of labels that are i as before, we select xi and ai to be the amounting value for G, and we let yi and bi to be those for H. It is easy to verify that v0=x0+x0y0+x1y0′, v1=x1+x0y1+x1y1′, e0=a0+x0b0+x1b0′+x0y1+x1y0′, and e1=a1+x0b1+x1b1′+x0y0+x1y1′. Thus, v0−v1=x0−x1+x0y0−y1+x1y0′−y1′ and e0−e1=a0−a1+x0b0−b1+x1b0′−b1′−x0y0−y1+x1y0′−y1′. (1) When it comes to the proof, we only need to show that, for each specified combination of labeling, v0−v1≤1 and e0−e1≤1.


## 3. Results and Discussion

In this section, we show thatPn⊙Cm is logical labeling if and only if n,m≠1,3mod4.Lemma 1.
The coronaPn⊙C3 is logical if and only if n≠1.Proof.
Obviously,P1⊙C3 isomorphic to the complete graph K4. Since K4 is not logical, P1⊙C3 is not logical. Conversely, for P2⊙C3, we choose the labeling 01:010,101; hence, v0−v1=0 and e0−e1=1. So, P2⊙C3 is logical, see Figure 1. For P3⊙C3, we choose the labeling 000:011,111,010; hence, v0−v1=0 and e0−e1=0. So, P3⊙C3 is logical, see Figure 2. Now, we need to study the following four cases for n≥4.(i)
Case (1) (n≡0mod4): suppose that n=4r,r≥1. We select the labeling L4r:010,010,101,101,…,r−times for P4r⊙C3. Therefore, x0=x1=2r, a0=2r−1, a1=2r, y0=2, y1=1, y0′=1, y1′=2, b0=2, b0′=2, b1=1, and b1′=1. Hence, v0−v1=x0−x1+x0y0−y1+x1y0′−y1′=0 and e0−e1=a0−a1+x0b0−b1+x1b0′−b1′−x0y0−y1+x1y0′−y1′=−1. As an example, Figure 3 illustrates P4⊙C3. Thus, P4r⊙C3 is logical.(ii)
Case (2) (n≡1mod4): suppose that n=4r+1,r≥1. We select the labeling L4r1:010,010,101,101,…,r−times,010 for P4r+1⊙C3. Therefore, x0=2r, x1=2r+1, a0=2r−1, and a1=2r+1, and for the first 4r-vertices, y0=2, y1=1, y0′=1, y1′=2, b0=b0′=2, and b1=b1′=1, and for the cycle c3 which is connected to last vertex in P4r+1, we have z0=2, z1=1, c0=2, and c1=1, where zi and ci are the numbers of vertices and edges labeled by i in c3 that is connected to the last vertex of P4r+1. It is easy to verify that v0=x0+x0y0+x1−1y0′+z0=8r+2, v1=x1+x0y1+x1−1y1′+z1=8r+2, e0=a0+x0b0+x1−1b0′+x0y0+x1−1y1′+c0+1=14r+3, and e1=a1+x0b1+x1−1b1′+x0y1+x1−1y0′+c1+2=14r+3. It follows that v0−v1=0 and e0−e1=0. As an example, Figure 4 illustrates P5⊙C3. Thus, P4r+1⊙C3 is logical.(iii)
Case (3) (n≡2mod4): suppose that n=4r+2,r≥1. We choose the labeling L4r10:010,010,101,101,…,r−times,101,010 for P4r+2⊙C3. Therefore, x0=x1=2r+1, a0=2r, a1=2r+1, y0=2, y1=1, y0′=1, y1′=2, b0=2, b0′=2, b1=1, and b1′=1. Hence, v0−v1=0 and e0−e1=−1. As an example, Figure 5 illustrates P6⊙C3. Thus, P4r+2⊙C3 is logical.(iv)
Case (4) (n≡3mod4): suppose that n=4r+3,r≥1. We select the labeling L4r100:010,010,101,101,…,r−times,101,010,101 for P4r+3⊙C3. Therefore, x0=2r+2, x1=2r+1, a0=2r+2, and a1=2r, and for the first 4r-vertices, y0=2, y1=1, y0′=1, y1′=2, b0=b0′=1, and b1=b1′=2, and for the cycle c3 which is connected to last vertex of P4r+3, we have z0=1, z1=2, c0=1, and c1=2, where zi and ci are the numbers of vertices and edges labeled by i in c3 that is connected to the last vertex of P4r+3. Similar to Case 2, we conclude that v0−v1=0 and e0−e1=0. As an example, Figure 6 illustrates P7⊙C3. Hence, P4r+3⊙C3 is logical. Thus, the lemma is proved.Figure 1
Logical labeling ofP2⊙C3.Figure 2
Logical labeling ofP3⊙C3.Figure 3
Logical labeling ofP4⊙C3.Figure 4
Logical labeling ofP5⊙C3.Figure 5
Logical labeling ofP6⊙C3.Figure 6
Logical labeling ofP7⊙C3.Lemma 2.
Ifm≡0mod4, then the corona Pn⊙Cm between paths Pn and cycles Cm is logical for all n≥1.Proof.
Letm=4s, where s≥1; then, we label the vertices of all n copies of C4s as B0=L4s, i.e., y0=2s, y1=2s, b0=2s, and b1=2s. Suppose that n=4r+i, where r≥1 and i=0,1,2,3; then, for given values of i with 0≤i≤3, we may use the labeling Ai for Pn as shown in Table 1. Using the formulas v0−v1=x0−x1+ny0−y1 and e0−e1=a0−a1+nb0−b1+x1−x0y0−y1 and Table 1, we can compute the values appeared in the last two columns of Table 2. Since these values are 0, −1, or 1, P4r+i⊙C4s (0≤i≤3 and r≥1) is logical. As examples, Figure 7 illustrates P4⊙C4, Figure 8 illustrates P9⊙C4, Figure 9 illustrates P6⊙C4, and Figure 10 illustrates P7⊙C4. It is remaining to show that Pn⊙C4s, 1≤n≤3, is logical. We choose the labeling 0:L4s for P1⊙C4s. Figure 11 illustrates P1⊙C8. So, v0−v1=1 and e0−e1=0, and hence, P1⊙C4s is logical. We select the labeling 01:L4s,L4s for P2⊙C4s. As an example, Figure 12 illustrates P2⊙C4. So, v0−v1=0 and e0−e1=1, and hence, P2⊙C4s is logical. Finally, we choose the labeling 001:L4s,L4s,L4s for P3⊙C4s. As an example, Figure 13 illustrates P3⊙C4. So, v0−v1=1 and e0−e1=0, and hence, P3⊙C4s is logical. Thus, the lemma is proved.Table 1
Labeling ofPn.
n=4r+i,i=0,1,2,3Labeling ofPnx0x1a0a1i=0A0=L4r2r2r2r−12ri=1A1=L4r02r+12r2r2ri=2A2=L4r012r+12r+12r+12ri=3A3=L4r0112r+12r+22r+12r+1Table 2
Combinations of labeling.
n=4r+i,i=0,1,2,3m=4s+j,j=0PnCmv0−v1e0−e1i=00A0B00−1i=10A1B010i=20A2B001i=30A3B0−10Figure 7
Logical labeling ofP4⊙C4.Figure 8
Logical labeling ofP5⊙C4.Figure 9
Logical labeling ofP6⊙C4.Figure 10
Logical labeling ofP7⊙C4.Figure 11
Logical labeling ofP1⊙C8.Figure 12
Logical labeling ofP2⊙C4.Figure 13
Logical labeling ofP3⊙C4.Lemma 3.
Ifm is not congruent to 0mod4, then the corona S between paths Pn and cycles Cm is logical, for all n≥4 and m≥4.Proof.
Letn=4r+i (i=0,1,2,3 and r≥1) and m=4s+j (j=1,2,3 and s≥1); then, for a given value of i with 0≤i≤3, we use the labeling Ai or Ai′ for Pn, as shown in Table 3. For a given value of j with 1≤j≤3, we used the labeling Bj or Bj′ for all the n copies of Cm, where Bj is the labeling of all copies of Cm which are joined to the vertices of Pn labeled 0 in Ai or Ai′ and Bj′ is the labeling of all copies of Cm which are joined to the vertices of Pn labeled 1 in Ai or Ai′ as given in Table 3. Figures 14–17 illustrate the examples P4⊙C5, P5⊙C5, P6⊙C5, and P7⊙C5, respectively. Using Table 3 and formulas v0−v1=x0−x1+x0y0−y1+x1y0′−y1′ and e0−e1=a0−a1+x0b0−b1+x1b0′−b1′−x0y0−y1+x1y0′−y1′. The numbers shown in the last two columns of Table 4 can be calculated. Because all of these numbers are either −1, 0, or 1, the lemma is proved.Table 3
Labeling ofPn and Cm.
n=4r+i,i=0,1,2,3Labeling ofPnx0x1a0a1i=0A0=L4r2r2r2r−12ri=1A1=L4r02r+12r2r2rA1′=0L4r2r+12r2r−12r+1i=2A2=L4r012r+12r+12r+12ri=3A3=L4r0012r+22r+12r+12r+1A3′=L4r1002r+22r+12r2r+2m=4s+j,j=1,2,3Labeling ofCmy0y1b0b1j=1B1=L4s12s2s+12s2s+1j=2B2=L4s012s+12s+12s+22sj=3B3=L4s0112s+12s+22s+22s+1m=4s+j,j=1,2,3Labeling ofCmy0′y1′b0′b1′j=1B1′=L4s02s+12s2s2s+1j=2B2′=L4s102s+12s+12s2s+2j=3B3′=L4s1002s+22s+12s2s+3Figure 14
Logical labeling ofP4⊙C5.Figure 15
Logical labeling ofP5⊙C5.Figure 16
Logical labeling ofP6⊙C5.Figure 17
Logical labeling ofP7⊙C5.Table 4
Combinations of labeling.
n=4r+i,i=0,1,2,3m=4s+j,j=1,2,3PnCmv0−v1e0−e101A0B1, B1′0−102A0B2, B2′0−103A0B3, B3′0−111A1B1, B1′0012A1′B2, B2′1013A1′B3, B3′0021A2B1, B1′0122A2B2, B2′0123A2B3, B3′0131A3B1, B1′0032A3′B2, B2′1033A3′B3, B3′00Lemma 4.
The coronaP1⊙Cm is logical for all m≥3 if and only if m≠3mod4.Proof.
Ifm≡3mod4, then it is easy to verify that every vertex of P1⊙Cm has an odd degree; also, the sum of its size and order is congruent to 2mod4. Consequently, by [13], the corona P1⊙C3 is not logical. Conversely, suppose that m=4s+j, where j=0,1,2, the following labelings are appreciated: 0:L4s for P1⊙C4s, 0:L4s1 for P1⊙C4s+1, and 0:L4s11 for P1⊙C4s+2. These three cases are shown in Figures 18–20. As a result, the lemma is established.Figure 18
Logical labeling ofP1⊙C4.Figure 19
Logical labeling ofP1⊙C5.Figure 20
Logical labeling ofP1⊙C6.Lemma 5.
The coronaPn⊙Cm, where n=2,3, are logical for all m≥4.Proof.
We have two cases:(i)
Case (1) (n=2): suppose that m=4s+j, where s≥1 and j=0,1,2,3. The four possible subcases should be investigated for m.(i)
Subcase (1.1) (m=4s): we select the labeling 01:L4s,L4s for P2⊙C4s. Therefore, x0=x1=1, a0=1, a1=0, y0=2s, y1=2s, b0=2s, b1=2s, y0′=2s, y1′=2s, b0′=2s, and b1′=2s. As an example, Figure 21 illustrates P2⊙C4. Hence, v0−v1=0 and e0−e1=1. Thus, P2⊙C4s is logical.(ii)
Subcase (1.2) (m=4s+1): we choose the labeling 01:L4s1,L4s0 for P2⊙C4s+1. Therefore, x0=x1=1, a0=1, a1=0, y0=2s, y1=2s+1, b0=2s, b1=2s+1, y0′=2s+1, y1′=2s, b0′=2s, and b1′=2s+1. As an example, Figure 22 illustrates P2⊙C5. Hence, v0−v1=0 and e0−e1=1. Thus, P2⊙C4s+1 is logical.(iii)
Subcase (1.3) (m=4s+2): we select the labeling 01:L4s10,L4s01 for P2⊙C4s+2. Therefore, x0=x1=1, a0=1, a1=0, y0=2s+1, y1=2s+1, b0=2s, b1=2s+2, y0′=2s+1, y1′=2s+1, b0′=2s+1, and b1′=2s. As an example, Figure 23 illustrates P2⊙C6. Hence, v0−v1=0 and e0−e1=1. Thus, P2⊙C4s+2 is logical.(iv)
Subcase (1.4) (m=4s+3): we choose the labeling 01:L4s110,L4s001 for P2⊙C4s+3. Therefore, x0=x1=1, a0=1, a1=0, y0=2s+1, y1=2s+2, b0=2s, b1=2s+3, y0′=2s+2, y1′=2s+1, b0′=2s+2, and b1′=2s+1. As an example, Figure 24 illustrates P2⊙C7. Hence, v0−v1=0 and e0−e1=1. Thus, P2⊙C4s+3 is logical.(ii)
Case (2) (n=3): suppose that m=4s+j, where s≥1 and j=0,1,2,3. For m, we should investigate the four subcases indicated below.(i)
Subcase (2.1) (m=4s): we select the labeling 001:L4s,L4s,L4s for P3⊙C4s. Therefore, x0=2, x1=1, a0=1, a1=1, y0=2s, y1=2s, b0=2s, b1=2s, y0′=2s, y1′=2s, b0′=2s, and b1′=2s. As an example, Figure 25 illustrates P3⊙C4. Hence, v0−v1=1 and e0−e1=0. Thus, P3⊙C4s is logical.(ii)
Subcase (2.2) (m=4s+1): we choose the labeling 001:L4s1,L4s1,L4s0 for P3⊙C4s+1. Therefore, x0=2, x1=1, a0=1, a1=1, y0=2s, y1=2s+1, b0=2s, b1=2s+1, y0′=2s+1, y1′=2s, b0′=2s, and b1′=2s+1. As an example, Figure 26 illustrates P3⊙C5. Hence, v0−v1=0 and e0−e1=0. Thus, P3⊙C4s+1 is logical.(iii)
Subcase (2.3) (m=4s+2): we select the labeling 010:0L4s1,1L4s0,0L4s1 for P3⊙C4s+2. Therefore, x0=2, x1=1, a0=2, a1=0, y0=2s+1, y1=2s+1, b0=2s, b1=2s+2, y0′=2s+1, y1′=2s+1, b0′=2s+2, and b1′=2s. As an example, Figure 27 illustrates P3⊙C6. Hence, v0−v1=1 and e0−e1=0. Thus, P3⊙C4s+2 is logical.(iv)
Subcase (2.4) (m=4s+3): we choose the labeling 010:L4s110,L4s001,L4s110 for P3⊙C4s+3. Therefore, x0=2, x1=1, a0=2, a1=0, y0=2s+1, y1=2s+2, b0=2s, b1=2s+3, y0′=2s+2, y1′=2s+1, b0′=2s+2, and b1′=2s+1. As an example, Figure 28 illustrates P3⊙C7. Hence, v0−v1=0 and e0−e1=0. So, P3⊙C4s+3 is logical. Thus, the lemma is proved.
The following theorem can be established as a result of all previous lemmas.Figure 21
Logical labeling ofP2⊙C4.Figure 22
Logical labeling ofP2⊙C5.Figure 23
Logical labeling ofP2⊙C6.Figure 24
Logical labeling ofP2⊙C7.Figure 25
Logical labeling ofP3⊙C4.Figure 26
Logical labeling ofP3⊙C5.Figure 27
Logical labeling ofP3⊙C6.Figure 28
Logical labeling ofP3⊙C7.Theorem 1.
The coronaPn⊙Cm is logical for all n≥1 and m≥3 if and only if n⋅m≠1,3mod4.


## 4. Conclusions

In this paper, we test the logical labeling of corona product of paths and cycle graphs. We found thatPk⊙Cm is logical, for all n≥1 and m≥3 if and only if n⋅m≠1,3mod4. In future work, we can extend this work by combining the various graphs with other mathematical computations to illustrate logical labeling.



---

*Source: 2312206-2022-02-10.xml*