Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

d -Lucky Labeling of Some Special Graphs

Zaib Hassan Niazi, Muhammad Awais Tariq Bhatti, Muhammad Aslam, Yasir Qayyum, Muhammad Ibrahim, Ather Qayyum*

Department of Mathematics, Institute of Southern Punjab Multan Pakistan

Abstract: Consider as labeling of graph ’s vertices. The weight for vertex x is specified as where shows the vertex x’s degree, shows the u’s open neighborhood and λ(y) shows the label for vertex y. In [1] M. Miller et al. define d-lucky labeling that is similar to the graph vertex coloring. The labeling λ is said to be d−lucky labeling of graph G if for each adjacent pair of vertices x and y in G. The least positive integer n such that G has a d-lucky labeling with {1, 2, ..., n} as the set of labels is known as d -lucky number of a graph G represented as In this paper we investigated the d-lucky number for jelly fish graph, coconut tree, kite graph, complete binary tree and generalized theta graph.

Keywords: lucky labeling, d -lucky labeling, jelly fish graph, coconut tree, kite graph, complete binary tree, generalized theta graph

Received November 01, 2022; Revised December 05, 2022; Accepted December 14, 2022

Citation: Zaib Hassan Niazi, Muhammad Awais Tariq Bhatti, Muhammad Aslam, Yasir Qayyum, Muhammad Ibrahim, Ather Qayyum, d -Lucky Labeling of Some Special Graphs. American Journal of Mathematical Analysis, 10 (1). 3-11. January 2022. doi:10.12691/ajma-10-1-2

1. Introduction

One of the most researched topics in graph theory is graph coloring. It is the process of assigning labels called color to the components of a graph subject to certain constraints. The analysis of proper labeling was started by Karonski, Luczak, and Thomason. The rule about using colors comes from coloring a map’s nations, where each face is precisely colored. Vertex coloring, also known as proper labeling, is a method of coloring a graph’s vertices such that no two neighboring vertices have the same color. The issue of proper labeling has a wide range of solutions and has recently gained a lot of attention. See [2,3,4,5] and [11,12] for more information. Networking, image segmentation, clustering, image capturing, and data mining are only a few of the computer science research fields where graph coloring is used.

There is a wide range of labeling procedures available in the literature that lead to proper graph vertex coloring. For a mapping a proper vertex coloring is obtained through Lucky labeling [6,7] Vertex-labeling by product [8], Vertex-labeling by gap, Vertex-labeling by degree and Vertex-labeling by maximum degree [8]. For a mapping , a proper vertex coloring is obtained through Edge-labeling by sum [9], Edge-labeling by product [5] and Edge-labeling by gap. In this paper we use the d -lucky labeling and compute the d -lucky number of some special graphs.

2. Jelly Fish Graph J(p,q)

Jelly fish graph defined in [10] can be constructed by a 4-cycle by attaching and via an edge and p pendent edges are attached with and and q pendent edges with . The Jelly fish graph containing vertices and edges. The vertex and edge collections of are listed below.

and

is known as upper central node, is known as left central node, is known as lower central node and is known as right central node. where and where are one-degree pendent nodes.

The Jelly fish graph accepts d-lucky labeling, as shown in the next theorem and

Figure 1. Jelly fish graph J(p, q)

Theorem 2.1. The Jelly fish graph where accepts d-lucky labeling with

Proof: Consider as labeling of graph’s vertices. The weight for vertex x is specified as

where shows the vertex x’ s degree, shows the u ’s open neighborhood and λ(y) shows the label for vertex y. The proof s divided into 4 separate cases for where .

Case. 1: For p = q = 1

is upper central node has and other 3 -adjacent vertices are labeled as 1. So

Similarly is lower central node having So

The left central node and right central node have The vertex is connected to the vertices, and also with pendent vertex having Likewise, the vertex is connected to the vertices and also with pendent vertex having So,

and

On the other side, the vertex is connected to vertex having So

Likewise, the vertex is connected to vertex having So

Case. 2: For p = 1 and q ˃ 1

The upper central node having and a11 other 3-adjacent vertices are labeled as 1. So

Likewise lower central node also having So

The left central node has The vertex is connected to the vertices and pendent node having So

The left central vertex is connected to a pendent node having So

The right central node has The vertex connected to vertices and with one-degree pendent nodes such that where So

The q pendent nodes having So

Figure 2. d -lucky labeling of J(5,7)

Case. 3: For q = 1, p > 1

This case is identical to previous case 2. All central nodes labeled as in case 2 with is connected to vertices and as well as a single pendent vertex As a result, Similarly the vertex connected to vertices and as well as the p pendent vertices where As a result, Every pendent vertex has the same weight as mentioned in previous case 2.

Case 4: For p, q > 1

The upper central node having and a11 other 3-adjacent vertices are labeled as 1. So.

Similarly is lower central node also having So

The left central node has The left central node is connected to vertices as well as pendent vertices such that where So

The p pendent nodes having As a result

The right central node has The vertex connected to vertices as well as pendent vertices such that where So

The q pendent nodes having So

It’s simple to verify that the weights of all neighboring nodes are different and brings the evidence to a close.

Figure 3. Weights of J(5,7)

3. Coconut Tree CT(p,q)

Coconut tree is formed by appending q new pendent edges to the last node of path Pp as define in [10].

The Coconut tree CT (p, q) containing p + q + 4 vertices and p + q + 5 edges. The vertex and edge collections of CT (p, q) are listed below.

and

The vertices of path Pp are represented by and the pendent nodes of degree one are represented by .

Coconut tree CT (p, q) accepts d-lucky labeling, as shown in the next theorem and

Figure 4. Coconut Tree CT(p,q)

Theorem 3.1. Coconut tree CT (p, q) accepts d-lucky labeling with

Proof: Consider as labeling of graph’s vertices. The weight for vertex x is specified as

where shows the vertex x’s degree, shows the u’s open neighborhood and λ(y) shows the label for vertex y. The proof s divided into 2 separate cases for CT (p, q) where .

Case. 1: For p = q = 1

The path Pp has single node with and The pendent node is with As a result,

and

Case 2: For p > 1, q ≥ 1 Or p ≥ 1, q > 1

Figure 5. d -lucky labeling of CT(7,7)

The vertices of path Pp at locations 4k where k = 1, 2, ..., h: 4h ≤ p, are labeled with 2 and all other vertices (i = 1, 2, ..., p ) are labeled with 1. All q pendent nodes where 1 ≤ j ≤ q are labeled with 1. The first node x₁ of path Pp has

With the exception of end node, all other vertices that located at even locations of path Pp have weights

Similarly except the end node, all other vertices that located at odd locations of path Pp have weights

If pendent nodes are attached to a vertex which located at location 4k where k = 1, 2, ..., h : 4h ≤ p of path Pp then

Otherwise

where j = 1, 2, ..., q. If the end node of path Pp is located at position 4k + 1 then otherwise

It’s simple to check that the weights of all neighboring nodes are different and brings the evidence to a close.

Figure 6. d -lucky labeling of CT(7,7)

4. (p, q)−Kite Graph

As specified in [10], a (p, q)−kite is a cycle of length p with q−edges path (the tail) connects to one node of cycle. In particular, the (p, 1)−kite is a cycle of length p with an edge fixed to one vertex of cycle. The flag graph denoted by is also known as (p, q)−kite. A (p, q)−kite containing p + q vertices and p + q edges. The vertex and edge collections of (p, q)−kite are listed below.

and

Figure 7. (p, q) -Kite

The vertices of cycle Cp are represented by where 1 ≤ i ≤ p and the vertices of path Pq where 1 ≤ j ≤ q are represented by

The (p, q) kite graph accepts d-lucky labeling, as shown in the next theorem and

Theorem. A (p, q)−kite accepts d-lucky labeling with

Proof: Consider as labeling of graph ’s vertices. The weight for vertex x is specified as

where shows the vertex x’ s degree, shows the u ’s open neighborhood and λ(y) shows the label for vertex y. The proof s divided into 3 separate cases for (p, q)−kite graph.

Case. 1: For p = 3, (3, q)−kite q ≥ 1.

Consider as the first node in cycle C₃ with a tail, so and is a node with and is a node with If the path’s first vertex is labeled with 1 than

and

Consider vertex as the first vertex of path Pq that is attached to vertex of cycle C₃. So has and each abeled as 1. So

The node of Pq has and each labeled as 1 and 2. So

After assigning the labels to of Pq, each node where 1 ≤ j ≤ q is labeled as 1 i.e. with exception of nodes that located at locations 4k + 3 where k = 1, 2, ..., h : 4h + 3 ≤ q are labeled with 2. The nodes where 1 ≤ j ≤ q which are located at locations at even locations of path Pq have

Likewise, the nodes where 1 ≤ j ≤ q that lie at odd locations of path Pq have

If end vertex path Pq lies at position 4a where a ≥ 1 then weight

otherwise

Case 2: For p > 3, p ≠ 4k − 1 where k ∈ N and q ≥ 1.

Each node where of Cp which located at location 4a where a = 1, 2, ..., l │4l ≤ p is labeled with 2 and remaining nodes are labeled with 1. As a result, nodes which located at even locations of cycle Cp have

Likewise the vertices that lies at odd positions of cycle Cp have weights

If p is a multiple of 4 then the first vertex y₁ has weight

otherwise weight

Now consider the vertex x₁ as the first vertex of path Pq that is adjacent to vertex y₁ of cycle Cp. The vertex x₁ has deg(x₁) = 2, λ(x₁) = 1 and each N (x₁) is labeled with 1. As a result, weight

The node x₂ of Pq has deg(x₂) = 2 and N (x₂) are labeled as 1 and 2. So,

After assigning the labels to x₁, x₂ and x₃ of path Pq every node xj where 1 ≤ j ≤ q has λ(xj) = 1 except nodes that located at positions 4k + 3 where k = 1, 2, ..., h : 4h + 3 ≤ q are labeled with 2. Vertices xj where 1 ≤ j ≤ q that lies at even positions of path Pq have weights

Likewise, the vertices xj where 1 ≤ j ≤ q that lies at even positions of path Pq have weights

If the end vertex of path Pq located at location 4a where a ≥ 1 then

Otherwise weight

Case 3: when p > 3 and p = 4k − 1 where k ≥ 1 and q ≥ 1.

Consider y₁ as the first node of Cp with a tail. Each node yi where 1 ≤ i ≤ p which located at location 4a where a = 1, 2, ..., l : 4l ≤ p and node which located at location Cp − 1 are labeled with 2 i.e. λ(yi) = 2 and remaining nodes are labeled with 1. The vertices which located at even locations of cycle Cp have

The vertex yp-2 has weight

Vertex yp has

The vertices which located at odd locations of cycle Cp have

The first vertex y₁ has weight

The path Pq is labeled as described in Case 2.

It’s simple to check that the weights of all neighboring nodes are different and brings the evidence to a close.

Figure 8. d -lucky labeling of (9,3)-Kite

Figure 9. Weights of (9,3)-Kite

5. The Complete Binary Tree CBT (l)

According to [10], a binary tree has precisely a single vertex (the root node) with degree 2 and each of remaining nodes has degree 1 or 3. A l level complete binary tree CBT (l) having depth l is a binary tree where every internal node (except root node) has a degree of three and all the pendent nodes are at level l.

A l level complete binary tree CBT (l), containing vertices and edges. The vertex and edge collections of l level complete binary tree CBT (l) are listed as below.

and

The root vertex at level 0 is represented by The vertices at level p are represented by where

Figure 10. Complete Binary Tree CBT (l)

The l level complete binary tree CBT (l) ∀ l ≥ 1 accepts d-lucky labeling, as shown in the next theorem and

Theorem 5.1. A complete binary tree of level l accepts d−lucky labeling with

Figure 11. d -lucky labeling of CBT (4)

Figure 12. Weights of CBT (4)

Proof: Consider as labeling of graph ’s vertices. The weight for vertex is specified as

where shows the vertex x’ s degree, shows the u ’s open neighborhood and λ(y) shows the label for vertex y. Assume vertex as root vertex at level 0 with two adjacent nodes at level 1. As a result, deg(x₀) = 2 with every N (x₀) is labeled with 1. So weight

Except root vertex (vertex at level 0) all other vertices have degree 1 or 3.

Case 1: Vertices with a degree of 3.

The odd-level vertices of degree 3.

Let lies at level p with and every at levels p − 1 and p + 1 are labeled with 1. So weight

The even-level vertices of degree 3.

Let lies at level p with , there is also a single with the label 2 and the other two vertices with the label 1. So

Case 2: Vertices with a degree of 1.

The node lies at level l with If is labeled with 1 then

Otherwise is labeled with 2 having

It’s simple to check that the weights of all neighboring nodes are different and brings the evidence to a close.

6. Generalized Theta Graph θg(L⁽t⁾)

Each theta graph in consists of t internally disjoint paths and each one has t + 2 vertices. Each path in each theta has a specific common node where 1 ≤ n ≤ g and these internally disjoint paths have a common end vertex

A generalized theta graph containing vertices and edges. The vertex and edge collections for are listed below.

and

The generalized theta graph accepts d-lucky labeling, as shown in the next theorem with

Theorem 6.1. A generalized theta graph accepts d-lucky labeling with

Proof: Consider as labeling of graph’s vertices. The weight for vertex is specified as

where shows the vertex x’ s degree, shows the u ’s open neighborhood and λ(y) shows the label for vertex y.

Figure 13. Generalized theta graph θg(L⁽t⁾)

Each path which starting at node and ending at node has and where a = 1, 2, ..., t, , b = 1, 2, ..., t , c = 1, 2, ..., g , with exception of nodes that located at locations 4k where 4k ≤ t , are labeled with 2. If last node is located at location 4 k than otherwise Common starting node of every path has

The nodes of path which placed at even locations of path (except ending node ) have

The nodes of path which placed at odd locations of path (except ending node ) have weights

If last node of path placed at location 4k + 1 than

Figure 14. d -lucky labeling of θ₄(5⁴)

Figure 15. Weights of θ₄(5⁴)

Otherwise weight,

It’s simple to check that the weights of all neighboring nodes are different and brings the evidence to a close.

7. Conclusion

In this paper we have used a newly defined labeling called d-lucky labeling and a graph that satisfies d-lucky labeling called d-lucky graph. d-lucky labeling of some special classes of graphs like jelly fish graph, coconut tree graph, kite graph, complete binary tree graph, and generalized theta graph are investigated.

References

[1]   | Mirka Miller, Indra Rajasingh, D. Ahima Emilet, D. Azubha Jemilet, d Lucky Labeling of Graphs, 3rd International Conference on Recent Trends in Computing 2015(ICRTC-2015).
[2]   | S. Czerwinski, J. Grytczuk, V. Zelazny, Luckying labelings of graphs, Information Processing Letters, 109(18) (2009), 1078-1081.
[3]   | G. Chartrand, F. Okamoto, P. Zhang, The sigma chromatic number of a graph, Graphs and Combinatorics, 26(6) (2010), 755-773.
[4]   | M. Karonski, T. Luczak, A. Thomason, Edges weights and vertex colours, Journal of Combi- natorial Theory, Series B, 91(1) (2004), 151-157.
[5]   | Ali Asghar, Ather Qayyum and Noor Muhammad, Different Types of Topological Structures by Graphs, European Journal of Mathematical Analysis, 3 (2022).
[6]   | A. Ahadi, A. Dehghan, M. Kazemi, E. Mollaahmadi, Computation of lucky number of planar graphs is NP-hard, Inform. Process. Lett., 112(4) (2012), 109-112.
[7]   | A. Deghan, M. R. Sadeghia, A. Ahadi, The complexity of sigma chromatic number of cubic graphs, Discrete Appl. Math., submitted.
[8]   | A. Dehghan, M.R. Sadeghi, A. Ahadi, Algorithmic complexity of proper labeling problems, Theoretical Computer Science, 495 (2013), 25-36.
[9]   | A. Dudek and D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math-ematics and Theoretical Computer Science, 13(3) (2011), 45-50.
[10]   | K. Manimekalai, K. Thirusangu, Pair Sum Labeling of some Special Graphs, International Journal of Computer Applications, 69(8) (2013).
[11]   | Ali Asghar, Ather Qayyum, Noor Muhamamd, Different Types of Topological Structures by Graphs, European Journal of Mathematical analysis, 3(2022).
[12]   | Generalization of Fixed-Point Approximation for Contraction and Suzuki generalized non-Expansive Mappings in Banach Domain, International journal of analysis and applications, 20 (65), (2022).