Using path coloring of graphs for communication in social networks
Dhanyashree, K. N. Meera, Said Broumi · Journal of Intelligent & Fuzzy Systems · 2023
An L ( p 1 , p 2 , p 3 , … , p m )- labeling of a graph G , has the vertices of G assigned with non-negative integers, such that the vertices at distance j should have at least p j as their label difference. If m = 3 and p 1 = 3, p 2 = 2, p 3 = 1, it is called an L (3, 2, 1)-labeling which is widely studied in the literature. In this paper, we define an L (3, 2, 1)-path coloring of G as a labeling g : V ( G ) → Z + such that between every pair of vertices there exists at least one path P where in the labeling restricted to this path is an L (3, 2, 1)-labeling. Among the labels assigned to any vertex of G under g , the maximum label is called the span of g . The L (3, 2, 1)-connection number of a graph G , denoted by k 3 c ( G ) is defined as the minimum value of span of g taken over all such labelings g . We call graphs with the special property that k 3 c ( G ) = | V ( G ) | as L (3, 2, 1)-path graceful. In this paper, we obtain k 3 c ( G ) of graphs that possess a Hamiltonian path and carry forward the discussion to certain classes of graphs which do not possess a Hamiltonian path, which is novel to this paper. Although different kinds of labeling are studied in the literature with different mathematical constraints imposed, the idea of showing the existence of a graph with a given number as its minimum labeling number has rarely been addressed. We show that given any positive integer, there always exists an L (3, 2, 1)-path graceful graph with the given integer as its k 3 c ( G ), thus addressing the inverse question. Finally exploiting the fact that there is no gap on the k 3 c ( G ) number line, we give an application of path colorings for secure communication on social networking sites. Efforts to deploy graph coloring in task scheduling, interference-free transmission, etc have been dealt by earlier researchers. In this paper, we deploy the L (3, 2, 1)-path coloring technique defined by us for secure communication in social networks, which has not been dealt with so far.