SciresolSciresolhttps://indjst.org/author-guidelinesIndian Journal of Science and Technology0974-564510.17485/IJST/v15i39.1154research articleProper d-Lucky Labeling of Rooted Products and Corona Products of Certain GraphsKujurChiranjilalchiranji@yahoo.com1Assistant Professor, St. Joseph’s CollegeWest Bengal - 734426, India1710202215392021315202210820222022Abstract
Objectives:To examine rooted products graph and corona product of path graph with itself and cycle graph with itself for the existence of d-lucky labeling. Methods:In this study, d-lucky number for Rooted product graph of path graph to path graph (Pn∘Pn) and Corona product graph (Pn⊙Pn) are computed. Method of construction is used throughout this paper to prove the theorems. Findings:Rooted products and corona products of path with itself and cycle graph with itself admit d-lucky labeling and d-lucky numbers for the same are obtained. Novelty: d-lucky numbers for some graphs are obtained by some authors but for rooted product of path with itself and corona products of path with itself and cycle with itself are new findings.
Lucky labeling of graph is an extension of graph labeling, a lot of work has been done in this area. Recently proper lucky labeling of Quadrilateral Snake graphs was published by Sateesh Kumar et al 1. Another variant of lucky labeling was further extended into d-lucky labeling by Indra Rajasingh et al 2. d-lucky labeling has been in studied for various graphs, this concept is being extended as proper d-lucky labeling by E. Esakkrammal et al 3. Lower bound of d-lucky number for certain graphs were found by Sandi Klavzar et al 4.
Proper d-lucky labeling for Rooted Product of PnoPn and CnoCn
For a vertex u in a graph G, let Nu={v∈V(G)/uv∈E(G) and Nu=Nu∪u. Let l:VG→{1,2,…,k} be a labeling of vertices of a graph G by positive integers. Define Cu=∑v∈N(u)lv+d(u), where d(u) denotes the degree ofu. Define a labeling l as d-lucky if Cu≠C(v), for every pair of adjacent vertices u and v in G. The d-lucky number of a graph G, denoted byɳdl(G), is the least positive k such that G has a d-lucky labeling with {1,2,…,k} as the set of labels. 2
Given a graph G of order n and a graph H with root vertex v , the rooted product graph GᴏH is defined as the graph obtained from G and H by taking one copy of G and n copies of H and identifying the vertex ui of G with the vertex v in the ith copy of H for every 1≤i≤n. We take first rooted product path Pn with itself and then cycle graph Cn with itself and compute the d-lucky labeling for them.
Theorem 1.1The Rooted product of Pn, Pn∘Pn admits proper d-lucky labeling and
Pn∘Pn, where n≥2.
Proof
The vertices of the product graph are labeled as shown below:
d-Lucky labeling
There are mn vertices of the product graph Pn○Pm . Here m=4 and n=5. Let fvij= the label assigned to the vertex vij. We define Svij=∑uij∈N(Vij)f(uij), as the sum of neighborhood of vertex vij, where N(vij) denotes the open neighborhood of vij∈V.
Label the vertices as given below:
For j=1,4,7,10,…,m.
i=1,2,3,…,n.
fVij-1=3i-1mod2+1.
For j=2,5,8,11,…,m.
i=1,2,3,…,n.
fVij-1=i+2mod2+1+{3imod2}
For j=3,6,9,…,m.
i=1,2,3,…,n.
fVij-1=i+1mod2+2.
It is seen that the vertices which are labelled as 1 in the row Vi0 will get neighborhood sum Svij=7 and Cu=10,except the corner vertices will get the neighbourhood sum as Svij=5 and Cu=7. The vertices in the row Vi0 labeled as 2 will have the neighbourhood sum as Svij=3 and Cu=6 except the corner vertex which will get the neighbourhood sum as Svij=2 and Cu=4. In the row Vij-1, j=4,7,10,…,m-1 the vertices with label 1 will get neighborhood sum as Svij= 5 and Cu=7and the vertices labeled as 2 will have the neighbourhood sum as Svij=4 and Cu=6. In the row Vij-1,j=m, the vertices with label 1 will get neighborhood sum as Svij=2 and Cu=3 and the vertices labeled as 2 will have the neighbourhood sum as Svij=3 and Cu=4. In the row Vij-1,j=2,5,8,…,m-1 the vertices with label 3 will get neighborhood sum as Svij= 3 and Cu=5 and the vertices labeled as 1 will have the neighbourhood sum as Svij=5 andCu=7. In the row Vij-1,j=m the vertices with label 3 will get neighborhood sum as Svij= 1 and Cu=2 and the vertices labeled as 1 will get the neighbourhood sum asSvij=2 and Cu=3. In the row Vij-1,j=3,6,9,…,m-1 the vertices labelled as 2 will get the neighbourhood sum as Svij= 4 and Cu=6 and the vertices with label 3 will have the neighbourhood sum as Svij=3 and Cu=5. In the row Vij-1,j=m the vertices with label 2 will get neighborhood sum as Svij= 3 and Cu=4 and the vertices labeled as 3 will get the neighbourhood sum asSvij=1 and Cu=2. We note that Cu≠Cv, for every pair of adjacent vertices u and v in Pn∘Pn.
Hence the Rooted product of PmandPn, Pm∘Pn admits proper d-lucky labeling and ηdl(Pm∘Pn)=3, where n≥2. (For illustration see Figure 2)
Proper d-Lucky Labeling of P6 o P6
Theorem 1.2:The Rooted product of Cn, Cn∘Cn admits proper d-lucky labeling and
ηdlCn∘Cn=2, when n is even 3, when n is odd , where ≥3.
Proof
Case 1: When n is even:
Label the vertices of the base cycle in clock wise direction with 1,2,1,2,1,2,…,1,2 in a cyclic manner until all the vertices of inner cycles receive a label. Next in the outer cycle whose one vertex is already labeled as 1, label rest of the vertices with 2 and 1 alternately such that no two adjacent vertices have the same labeling. In the outer cycle whose one vertex is labeled as 2, label rest of the vertices with 1 and 2 alternately such the no two adjacent vertices have the same labeling.
It is observed that the neighborhood sum S(u) for the outer cycle which is labeled as 1 are Su=4andCu=6 and for the vertex with label 2 has Su=2 and Cu=4.
For the inner cycle the neighborhood sum S(u) of the vertices with label as 1 has Su=1(n-2)2+2(n2)+4 and Cu=1(n-2)2+2(n2)+8. The vertices which are labeled as 2 will have Su=1(n2)+2(n-2)2+2 and Cu=1(n2)+2(n-2)2+4 Thus, it is noticed that no two adjacent vertices have the same C(u)'s. Hence the Rooted product of Cn, ηdlCn∘Cn=2 admits proper d-lucky labeling and ηdlCn∘Cn=2, where n≥3.
Case 2: when n is odd
Label the vertices of the base cycle in anti-clock wise direction with 1,2,3,1,2,3,….,1,2,3 in a cyclic manner and the last two vertices receive the label as 1,3. Next in the outer cycle whose one vertex is labeled as 1, label rest of the vertices in ant-clockwise direction as 3,1,3,1,….3,1 and the last vertex as 2. In the outer cycle whose one vertex is labeled as 2 , label rest of the vertices in anti-clockwise direction as 1,2,12,12,….1,2 alternately and the last vertex as 3. In the outer cycle whose one vertex is labeled as 3, label in anti-clockwise as 1,3 alternately and the last vertex as 2.
For n=3, the inner cycle vertices with label 1 have neighbourhood sums as Su=10,Cu=14, with label 2, Su=8,Cu=12, with label 3, Su=6andCu=10. The neighborhood sum S(u) for the outer cycle are Su=5 for the vertex with label as 1 and Cu=7. The vertex with label 2 of the outer cycle has Su=4 and Cu=6. The vertex with label 3 of the outer cycle has Su=3 and Cu=5.
For n≥4, it is observed that the neighborhood sum S(u) for the outer cycle are Su=4or5or6 for the vertex with label as 1 and Cu=6or7or8. The vertex with label 2 of the outer cycle has Su=2or4 and Cu=4or6. The vertex with label 3 of the outer cycle has Su=2or3 and Cu=4or5.
For the inner cycle the vertices with label 1, which is adjacent to vertices with label as 3 have Su=3(n-1)2+1(n-3)2+8 and Cu=3(n-1)2+1(n-3)2+12. For the vertices with label as 1and which is adjacent to vertices with label as 3 and 2 in the inner cycle have Su=3(n-1)2+1(n-3)2+7 and Cu=3(n-1)2+1(n-3)2+11. The vertex with label 2 will get Su=1(n-1)2+2(n-3)2+7 and Cu=1(n-1)2+2(n-3)2+11. The vertex with label 3 and adjacent to vertices with label as 1 in the inner cycle will have Su=1(n-1)2+2(n-3)2+5 and Cu=1(n-1)2+2(n-3)2+9. The vertex with label 3 and adjacent to vertices with label as 1 and 2 in the inner cycle will have Su=1(n-1)2+2(n-3)2+6 and Cu=1(n-1)2+2(n-3)2+10 Thus, it is observed that no two adjacent vertices have the same C(u)'s. Hence in this case the Rooted product of Cn, Cn∘Cn admits proper d-lucky labeling and ηdlCn∘Cn=3. (for illustration see Figure 3)
Proper d-lucky labeling ofC6∘C6
Hence the result.
Proper d- lucky labeling for Corona Product of Pn⊙Pnand Cn⊙Cn
The corona product of G and H is the graph G⊙H obtained by taking one copy of G, called the center graph, V(G) copies of H, called the outer graph, and making the ith vertex of G adjacent to every vertex of the ith copy of H, where 1≤i≤V(G). In this section corona product of Pn with Pn, Cn with Cn are taken and proper d-lucky number for the same are computed.
Theorem 2.1:The Corona product of Pn, Pn⊙Pn admits proper d-lucky labeling and ηdl(Pn⊙Pn)=4, where n≥2 .
Proof:
Label the vertices of the base path Pn alternately with 1,2,3,4. Other vertices of corona are labeled as follows: The vertex which is identified with the base path Pn, if it has the label 1 then label all other vertices alternately as 2,3. If it has the label as 2 then label all other vertices alternately as 1,4. If it has label as 3 then label all other vertices as 1,2 alternately and if it has label as 4, then label all other vertices as 1,2 alternately. For neighborhood sum two cases arise.
Case 1: when n is even:
Whenn=2, in the base vertices, the neighborhood sum Su=7 and Cu=10, for vertices with label 1, for the vertices labeled as 2, Su=5andCu=8. The vertices other than base vertices labeled as 1 has Su=5,Cu=7, labeled as 2 has Su=4,Cu=6 and labeled as 3 has Su=3andCu=5.
Whenn≥3, in the base vertices, the neighborhood sum Su={n25+2} and Cu={7n+62} for the end vertices with label 1. All other vertices with label as 1 have Su={n25+6} and Cu=7n+162 . Su={n25+1} and Cu=7n+42 for the end vertices with label 2 and all other vertices with label 2 will have Su={n25+4} and Cu=7n+122 . The vertex with label as 3 will get Su=3n+122 and Cu=5n+162. The end vertex with label as 4 will get Su=3n+62 and Cu=5n+82. All other vertices with label as 4 will have Su=3n+82 and Cu=5n+122.
For vertices other than the base vertices with label as 2 and adjacent to base vertex 1 will have Su=4and7 and Cu=6and10. The vertex labelled as 2 and adjacent to base vertex 3 will have Su=5,4 and Cu=8,6. And adjacent to base vertex with label as 4 will have Su=6,5andCu=9,7. Thus, it is noticed that no two adjacent Cu's are same.
Case 2: When n is odd:
In the base vertices, the neighborhood sum Su=5n+32 and Cu=7n+52, for the end vertices with label 1 and adjacent to vertex with label as 2. The vertices adjacent to vertex as label 4 will have Su=5n+72 and Cu=7n+92 . All other vertices with label as 1 will have Su=5n+112 and Cu=7n+152. Su=3n+32 and Cu=5n+52 for the end vertices with label as 3 and all other vertices with label as 3 will have Su=3n+112 and Cu=5n+152 . The Neighbourhood sum for all the vertices with label as 2 will be Su=5n+52 and Cu=7n+92. The neighbourhood sum for the vertices with label as 4 will be Su=3n+52 and Cu=5n+92 . All other vertices will have similar C(u)'s as Case 1.
No two adjacent vertices have the same S(u) and C(u). Hence the result follows. (for illustration see Figure 4).
Proper d-Lucky Labeling of P5⊙P5
Theorem 2.2:The Corona product of Cn, Cn⊙Cn admits proper d-lucky labeling and ηdlCn⊙Cn=3, when n is even 5, when n is odd , where n≥3 .
Proof
For this theorem two cases arise.
Case 1:when n is even
Label the vertices of the base cycle as 1,2 alternately. The vertices of outer cycle are labeled 2,3 alternately if it is adjacent to 1of the base cycle and are labelled as 1,3 alternately if it is adjacent to 2 of the base cycle.
The neighborhood sum S(u) for the vertices of outer cycles will be as follows: Su=8 and Cu=11 for the vertex with label as 1. Su=5 and Cu=8 for the vertex with label as 2. Su=4 and Cu=7 for the vertex with label as 3 and adjacent to the vertex with label as 2 of the base cycle. Su=5 and Cu=8 for the vertex with label as 3 and adjacent to the vertex with label as 1 of the base cycle.
The neighborhood sum S(u) for the base cycle will be as follows: The vertex with label as 1 will receive Su=5n+82 and Cu=7n+122. The vertex with label as 2 will have Su=4n+42 and Cu=6n+82. It is observed that no two adjacent vertices have the same S(u) and the same C(u) in this case. Hence ηdlCn⊙Cn, when n is even.
Case 2: when n is odd
Label the vertices of the base cycle in clockwise direction alternately with 2,1 and the last vertex is labeled as 3. Similarly, label the vertices of the outer cycle in anticlockwise direction with 2,3,4 in cyclic manner and the last vertex is labeled as 5. The vertices with label as 1 in the base cycle, label other vertices alternately as 1,3 and the last vertex as 4. The vertices labelled as 2 in the base cycle, label other vertices as 1,2 alternately and the last vertex as 4. The neighborhood sum S(u) and Cu are calculated similar to case 1 The neighborhood sum S(u) for the base cycle will be as follows: The vertices with label as 1 will receive Su=5n+82 and Cu=7n+122. The vertex with label as 2 will have Su=4n+42 and Cu=6n+82. It is observed that no two adjacent vertices have the same S(u) and the same C(u) in this case. Hence ηdlCn⊙Cn=5 , when n is odd.
It is noticed that no two adjacent vertices have the same S(u) and C(u) in this case. Hence ηdlCn⊙Cn=5 , when n is odd. (for illustration see the Figure 5)
Properd- Lucky Labeling of C6⊙C6 and C5⊙C5
Hence the result.
Conclusion
In this Paper proper d-lucky number for rooted graph Pn∘Pn, Pn∘Pn and corona graph Pn⊙Pn , Cn⊙Cn are computed and found as ηdl(Pn∘Pn)=3, where n≥2 ,
ηdlCn∘Cn=2, when n is even 3, when n is odd , where ≥3, and
ηdl(Pn⊙Pn)=4, where n≥2 , and
ηdlCn⊙Cn=3, when n is even 5, when n is odd , where n≥.
Acknowledgment
The author would like to acknowledge the contributions of the reviewers for their valuable suggestions to make the article better.
ReferencesKumarT VMeenakshiSLucky and Proper Lucky Labeling of Quadrilateral Snake Graphs202110851203912039https://doi.org/10.1088/1757-899X/1085/1/012039EsakkiammalEThirusanguKSeethalakshmiSProper d-Lucky labeling on arbitrary super subdivision of some graphs”201961595602http://www.j-asc.com/gallery/71-january-2019.pdfMillerMirkaRajasinghIndraEmiletD AhimaJemiletD Azubhad-Lucky Labeling of Graphs2015577667711877-0509Elsevier BVhttps://doi.org/10.1016/j.procs.2015.07.473KlavzarSandiRajasinghD IndraEmiletA Lower bound and several Exact Results on the d-lucky number”2019112arXvi:1903.07863