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.
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.
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 
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
 |
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.
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 
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
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 x1 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.
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
 |
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 C3 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 C3. 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 y1 has weight
 |
otherwise weight
 |
Now consider the vertex x1 as the first vertex of path Pq that is adjacent to vertex y1 of cycle Cp. The vertex x1 has deg(x1) = 2, λ(x1) = 1 and each N (x1) is labeled with 1. As a result, weight
 |
The node x2 of Pq has deg(x2) = 2 and N (x2) are labeled as 1 and 2. So,
 |
After assigning the labels to x1, x2 and x3 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 y1 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 y1 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.
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 
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 
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(x0) = 2 with every N (x0) 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.
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.
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
 |
Otherwise weight,
 |
It’s simple to check that the weights of all neighboring nodes are different and brings the evidence to a close.
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.
| [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). | ||
| In article | View Article | ||
| [2] | S. Czerwinski, J. Grytczuk, V. Zelazny, Luckying labelings of graphs, Information Processing Letters, 109(18) (2009), 1078-1081. | ||
| In article | View Article | ||
| [3] | G. Chartrand, F. Okamoto, P. Zhang, The sigma chromatic number of a graph, Graphs and Combinatorics, 26(6) (2010), 755-773. | ||
| In article | View Article | ||
| [4] | M. Karonski, T. Luczak, A. Thomason, Edges weights and vertex colours, Journal of Combi- natorial Theory, Series B, 91(1) (2004), 151-157. | ||
| In article | View Article | ||
| [5] | Ali Asghar, Ather Qayyum and Noor Muhammad, Different Types of Topological Structures by Graphs, European Journal of Mathematical Analysis, 3 (2022). | ||
| In article | View Article | ||
| [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. | ||
| In article | View Article | ||
| [7] | A. Deghan, M. R. Sadeghia, A. Ahadi, The complexity of sigma chromatic number of cubic graphs, Discrete Appl. Math., submitted. | ||
| In article | |||
| [8] | A. Dehghan, M.R. Sadeghi, A. Ahadi, Algorithmic complexity of proper labeling problems, Theoretical Computer Science, 495 (2013), 25-36. | ||
| In article | View Article | ||
| [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. | ||
| In article | View Article | ||
| [10] | K. Manimekalai, K. Thirusangu, Pair Sum Labeling of some Special Graphs, International Journal of Computer Applications, 69(8) (2013). | ||
| In article | View Article | ||
| [11] | Ali Asghar, Ather Qayyum, Noor Muhamamd, Different Types of Topological Structures by Graphs, European Journal of Mathematical analysis, 3(2022). | ||
| In article | View Article | ||
| [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). | ||
| In article | View Article | ||
Published with license by Science and Education Publishing, Copyright © 2022 Zaib Hassan Niazi, Muhammad Awais Tariq Bhatti, Muhammad Aslam, Yasir Qayyum, Muhammad Ibrahim and Ather Qayyum
This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit
https://creativecommons.org/licenses/by/4.0/
| [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). | ||
| In article | View Article | ||
| [2] | S. Czerwinski, J. Grytczuk, V. Zelazny, Luckying labelings of graphs, Information Processing Letters, 109(18) (2009), 1078-1081. | ||
| In article | View Article | ||
| [3] | G. Chartrand, F. Okamoto, P. Zhang, The sigma chromatic number of a graph, Graphs and Combinatorics, 26(6) (2010), 755-773. | ||
| In article | View Article | ||
| [4] | M. Karonski, T. Luczak, A. Thomason, Edges weights and vertex colours, Journal of Combi- natorial Theory, Series B, 91(1) (2004), 151-157. | ||
| In article | View Article | ||
| [5] | Ali Asghar, Ather Qayyum and Noor Muhammad, Different Types of Topological Structures by Graphs, European Journal of Mathematical Analysis, 3 (2022). | ||
| In article | View Article | ||
| [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. | ||
| In article | View Article | ||
| [7] | A. Deghan, M. R. Sadeghia, A. Ahadi, The complexity of sigma chromatic number of cubic graphs, Discrete Appl. Math., submitted. | ||
| In article | |||
| [8] | A. Dehghan, M.R. Sadeghi, A. Ahadi, Algorithmic complexity of proper labeling problems, Theoretical Computer Science, 495 (2013), 25-36. | ||
| In article | View Article | ||
| [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. | ||
| In article | View Article | ||
| [10] | K. Manimekalai, K. Thirusangu, Pair Sum Labeling of some Special Graphs, International Journal of Computer Applications, 69(8) (2013). | ||
| In article | View Article | ||
| [11] | Ali Asghar, Ather Qayyum, Noor Muhamamd, Different Types of Topological Structures by Graphs, European Journal of Mathematical analysis, 3(2022). | ||
| In article | View Article | ||
| [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). | ||
| In article | View Article | ||
