Using path coloring of graphs for communication in social networks.

An L (p₁, p₂, p₃, ... , 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₁ = 3, p₂ = 2, p₃ = 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_3c (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_3c (G) = |V (G) | as L (3, 2, 1)-path graceful. In this paper, we obtain k_3c (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_3c (G), thus addressing the inverse question. Finally exploiting the fact that there is no gap on the k_3c (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. [ABSTRACT FROM AUTHOR]