SciresolSciresolhttps://indjst.org/author-guidelinesIndian Journal of Science and Technology0974-564510.17485/IJST/v16i4.2146Research ArticleProper d-Lucky Number for Certain Rooted Product GraphsKujurChiranjilalchiranji@yahoo.com1Assistant Professor, St. Joseph’s CollegeDarjeeling, West Bengal, 734426India27120231642497112022221220222023Abstract

Objectives: In this study, rooted product of path with cycle, path with complete graph cycle with complete graph and complete graph with complete graphs are taken and examined for the existence of d-lucky labeling for the same. Methods: The rooted product graphs are obtained of path with cycle, path with complete graph, cycle with complete graph and complete graph with itself and then proper d-lucky numbers are obtained for the above mentioned graphs. Construction and descriptive method are used to prove the results. Findings: Proper d-lucky labeling for the said graphs are verified and proper d-lucky numbers for the same are obtained. Novelty: It involves the mathematical formulations which involves labeling the vertices of a graph in such a manner that no two adjacent vertices have the same labeling and the neighborhood sums and degree sums of the adjacent vertices are different, which gives rise to proper d-lucky labeling.

There are different types of labeling of graphs. According to one’s requirements various types of labeling are originating in this field. Proper d-lucky labeling is one such labeling of graph, which was defined by Mirka Miller et al 1. Recently a new labeling called d-lucky edge labeling was introduced and d-lucky edge number for path graph was determined by G. Rajini Ram et al 2. Proper lucky labeling and lucky edge labeling for extended duplicate graph of quadrilateral snake graph were investigated by P. Indira et al 3. The existence of an efficient zero ring labeling for some classes of trees and their disjoint union were studied by Dhenmar E. Chua et al 4. Lucky and Proper Lucky Labeling of Quadrilateral Snake Graphs were studied by T. V. Sateesh Kumar et al 5. d-lucky number for rooted product and corona product of certain graphs were obtained by Kujur C 6.

For a vertex u in a graph G, let Nu={v∈V(G)/uv∈E(G). Let l:VG→{1,2,…,k} be a labeling of vertices 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. Further if every pair adjacent vertices have different labels, then it is called proper d-lucky labeling and k is called proper d-lucky number, denoted by ηpdl(G).

Rooted product of graphs is defined by C. D. Godsil as, “Given a graph G of order n and a graph H with root vertex v, the rooted product graph G∘H (copies of H in G, symbol used for rooted product of G with 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”. In this paper rooted product of path with cycle, path with complete graph, cycle with complete graph and complete graph with complete graphs are taken and examined for the existence of d-lucky labeling for the same.

Result and Discussion

Theorem 1:

Rooted product of path with cycle,PnoCn admits proper d-lucky labeling and ηpdlPnoCn=4,n≥3.

Proof: Label the base vertices of path Pn with 1,4 alternately. There are two cases while labeling the vertices of Cn.

Case 1: When n is even

If its base vertex has received a label as 1then label all other vertices of Cn in clockwise direction with 3,1 alternately. If the base vertex of Cn has been labeled as 4, then label all other vertices in clockwise direction with 1,3 alternately.

Case 2: When n is odd

If the base vertex of Cn has received label as 1 then label all other vertices in clockwise direction with 3,1 alternately and label the last vertex with 2. If the base vertex of Cn has been labeled as 4, then label all other vertices in clockwise direction with 1,3 alternately.

The neighborhood sums s(u) and degree sums c(u) are calculated as follows:- In cycle Cn the vertices which are labeled as 3, get su=2 and cu=4, except the vertices which are adjacent to vertex with label as 2 get su=3 and cu=5 and the vertices which are adjacent to the vertex with label as 4 get su=5 and cu=7. The vertices which are labeled as 1 get su=6 and cu=8 except the vertices which are adjacent to the vertex with label 4 getsu=7 and cu=9. The vertices which are labeled as 2 have su=4 and cu=6.

In Pn the end vertex which are labeled as 1 have su=10 and cu=13 and all other vertices with the same label have su=14 and cu=18, when nis even.

su=9 and cu=12 for the end vertices which are labeled as 1, and all other vertices with the same label have su=13 and cu=17, when n is odd. The end vertices which are labeled as 4 have su=3 and cu=6, when n is even.

When n is odd su=5 and cu=8, for the end vertices which are labeled as 4. All other vertices which are labeled as 4 have su=4 and cu=8, when n is even. su=6 and cu=10, when n is odd (for illustration see Figure 1 ).

Proper d-lucky labeling with <inline-formula id="inline-formula-2fce199462c74e4f95315d25e6381cdd"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>c</mml:mi><mml:mo>(</mml:mo><mml:mi>u</mml:mi><mml:mo>)</mml:mo><mml:mo>'</mml:mo><mml:mi>s</mml:mi></mml:math></inline-formula> of <inline-formula id="inline-formula-cd06a050fd4647fc978726c8edc84455"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>5</mml:mn></mml:msub><mml:mi>o</mml:mi><mml:msub><mml:mi>C</mml:mi><mml:mn>6</mml:mn></mml:msub></mml:math></inline-formula> and <inline-formula id="inline-formula-ecb9b960eb0e46dd997badbd8050088c"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>8</mml:mn></mml:msub><mml:mi>o</mml:mi><mml:msub><mml:mi>C</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math></inline-formula>

It is observed that no two adjacent vertices have the same c(u)'s. Hence rooted product PnoCn admits proper d-lucky labeling and ηpdlPnoCn=4,n≥3.

Theorem 2:

Rooted product of path with complete graph, PmoKn admits proper d-lucky labeling and

ηpdlPmoKn=n,n≥3.

Proof:Label the base vertices of the path Pm with 1,2,3 in cyclic order. The vertices of Kn are labelled as follows: if the base vertex is labeled as 1, then all other vertices receive the label as 2,3,4..., n. If the base vertex is labeled as 2, then all the other vertices are labeled as 3,4, 5…, n,1. If the base vertex is labeled as 3, the rest of the vertices are labeled as 4,5,6,…n,2,1, and so on (for illustration see Figure 2 ).

Proper d-lucky labeling with <inline-formula id="inline-formula-860f676a60384e68a2097eaeef5051ba"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>c</mml:mi><mml:mo>(</mml:mo><mml:mi>u</mml:mi><mml:mo>)</mml:mo><mml:mo>'</mml:mo><mml:mi>s</mml:mi></mml:math></inline-formula> of <inline-formula id="inline-formula-160b0ac1e8004433ab93ab24dac2c9e8"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>5</mml:mn></mml:msub><mml:mi>o</mml:mi><mml:msub><mml:mi>K</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math></inline-formula>

The neighborhood sums and degree sums for Kn are calculated as follows:

fori=1,2,3,…n,n≥3

sui=nn+1-2i2 and

cui=nn+3-2(i+1)2, for all the vertices except the base vertices of Pn.

Neighborhood sum and degree sums for Pm are calculated as follows:

If a vertex is labeled as 1 and is a corner vertex adjacent to vertex with labeled as 2,

then su=nn+1-2(i-2)2 and cu=nn+3-2(i-2)2.

If the vertex is labeled as 1 and adjacent to the vertex with label as 3 which is corner vertex then, su=nn+1-2(i-3)2 and cu=nn+3-2(i-3)2 , all other vertices in Pn with label as 1 have su=nn+1-2(i-5)2 and cu=nn+3-2(i-6)2.

If the vertex has label as 2 which is not a corner vertex then su=nn+1-2(i-4)2 and cu=nn+3-2(i-1)2 and if it is corner vertex then, su=nn+1-2(i-1)2andcu=nn+3-2(i-1)2.

The corner vertex which has label 3 then su=nn+1-2(i-1)2 and cu=nn+3-2(i-1)2, all other vertices with label as 3 have s(u)=nn+1-2(i-3)2 and cu=nn+3-2(i-4)2.

It is observed that no two adjacent vertices have the same c(u)'s.

Therefor the rooted product PmoKn admits proper d-lucky labeling and ηpdlPmoKn=n,n≥3.

Theorem 3:

Rooted product of cycle with complete graph,CnoKn admits proper d-lucky labeling and ηpdlCnoKn=n,n≥3.

Proof:The proof is given for two cases.

Case1: when n is even.

Label the vertices of the base of Cn with 1,2 alternately. All other vertices of Kn are labeled as follows: If one of the vertices of Kn in the base of Cn is labeled as 1, then all other vertices are labeled as 2,3,4,..n respectively. If it is labeled as 2 then all other vertices are labeled as 3,4, 5…, n,1, respectively and so on till all the vertices of the graph are labeled.

The neighborhood sum and degree sum for Kn except for the base vertices of Cn are calculated as given below

fori=1,2,3,…n,n≥3

sui=nn+1-2i2 and cui=nn+3-2(i+1)2

In the base cycle of Cn the vertices which are labeled as 1 have sui=nn+1-2(i-4)2 and cui=nn+3-2(i-5)2.

The vertices which are labeled as 2 have sui=nn+1-2(i-2)2 and cui=nn+3-2(i-3)2.

Case 2: when n is odd.

Label the base vertices of Cn with 1,2 alternately and the last vertex with 3. All vertices of Kn are labeled as in case 1, except the vertices which are labeled as 3 in the base of Cn, label all other vertices of Kn as 4,5,6,…n,2,1 and so on till all the vertices are labeled (for illustration see Figure 3 ).

Proper d-lucky labeling with <inline-formula id="inline-formula-b69c62a34dc64c6d97471618e165ed4b"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>c</mml:mi><mml:mo>(</mml:mo><mml:mi>u</mml:mi><mml:mo>)</mml:mo><mml:mo>'</mml:mo><mml:mi>s</mml:mi></mml:math></inline-formula> of <inline-formula id="inline-formula-7283b42f8784463698357d8747535034"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>C</mml:mi><mml:mn>5</mml:mn></mml:msub><mml:mi>o</mml:mi><mml:msub><mml:mi>K</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math></inline-formula>

The neighborhood sums and degree sums of Cn are calculated as given below:-

If the vertex is labeled as 1 which is adjacent to vertices with label as 2 and 3, then sui=nn+1-2i-2(i-5)2 and cui=nn+3-2(i-6)2. All other vertices with label as 1 have sui=nn+1-2(i-4)2 and cui=nn+3-2(i-5)2. If the vertex is labeled as 2 and is adjacent to vertices with label as 3 and 1, then sui=nn+1-2(i-4)2 and cui=nn+3-2(i-5)2. All other vertices with label as 2 have sui=nn+1-2(i-2)2 and cui=nn+3-2(i-3)2. If the vertex is labeled as 3 then sui=nn+1-2(i-3)2 and cui=nn+3-2(i-4)2.

It is seen that in both the cases no two adjacent vertices have the same c(ui)'s. Hence the rooted product CnoKn admits proper d-lucky labeling and npdlCnoKn=n,n≥3.

Theorem 4:

Rooted product of complete graph with itself KnoKn, admits proper d-lucky labeling and ηpdlKnoKn=n,n≥3.

Proof: Label the base vertices of Knwith 1,2,3,…n respectively. Label the outer vertices of Kn as given below: if one of its vertices are labeled as 1 in the base vertex then label rest of the vertices as 2,3,4,…n. If one of its vertices in the base have label as 2, then label rest of the vertices of Kn as 3,4,5,…,n,1. Follow similar pattern of labeling for the rest of the vertices of outer Kn's till all the vertices are labeled (for illustration see Figure 4 ).

Proper d-lucky labeling with <inline-formula id="inline-formula-99f24db35c114c1b89e5eb564d0a4579"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>c</mml:mi><mml:mo>(</mml:mo><mml:mi>u</mml:mi><mml:mo>)</mml:mo><mml:mo>'</mml:mo><mml:mi>s</mml:mi></mml:math></inline-formula> of <inline-formula id="inline-formula-6c157a6b29084d14b9a36f960aab07ec"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>K</mml:mi><mml:mn>6</mml:mn></mml:msub><mml:mi>o</mml:mi><mml:mo> </mml:mo><mml:msub><mml:mi>K</mml:mi><mml:mn>6</mml:mn></mml:msub></mml:math></inline-formula>

The neighborhood sums and degree sums for outer vertices of Knare calculated as given bellow:

fori=1,2,3,4…,n

sui=nn+1-2i2 and cui=nn+3-2(i+1)2 .

The neighborhood sum and degree sum for inner vertices of Kn are calculate as given bellow:

fori=1,2,…n

sui=nn+1-2i and cui=nn+3-2(i+1).

It is observed that no two adjacent vertices have the same c(u)'s.

Hence the rooted product KnoKn admits proper d-lucky labeling and ηpdlKnoKn=n,n≥3.

( the operation CnoKn means Kn copies added in Cn, which is read as rooted product of Cn with Kn, this notation is used for simplification)

Conclusion

Proper d-lucky numbers for rooted product graphs of PmoCn, PmoKn, CnoKn and KnoKn are obtained and found to be ηpdlPmoCn=4, n≥3, ηpdlPmoKn=n, n≥3,ηpdlCnoKn=n , n≥3,ηpdlCnoKn=n, and ηpdlKnoKn=n , n≥3. The work could be continued for other rooted product graphs.

Acknowledgment

The author would like to acknowledge the reviewers for their valuable suggestions, which are incorporated in the article and thank them immensely for their contribution in making this paper better.

ReferencesMillerMirkaRajasinghIndraEmiletD AhimaJemiletD Azubhad-Lucky Labeling of GraphsRamG RajiniHemalathaSAnithaKD-lucky edge labeling of path familiesIndiraPSelvamBThirusanguKProper Lucky Labeling and Lucky Edge Labeling for the Extended Duplicate Graph of Quadrilateral SnakeDhenmarEChuaFrancisJosephHCampenaFloresto AFrancoEfficient Zero Ring Labeling of GraphsKumarT VMeenakshiSLucky and Proper Lucky Labeling of Quadrilateral Snake GraphsKujurChiranjilalProper d-Lucky Labeling of Rooted Products and Corona Products of Certain Graphs